[GitHub] MaxGekk commented on a change in pull request #23858: [SPARK-26955][CORE] Align Spark's TimSort to jdk11 implementation

[GitBox <gi...@apache.org>]

MaxGekk commented on a change in pull request #23858: [SPARK-26955][CORE] Align Spark's TimSort to jdk11 implementation
URL: https://github.com/apache/spark/pull/23858#discussion_r259008824
 
 

 ##########
 File path: core/src/main/java/org/apache/spark/util/collection/TimSort.java
 ##########
 @@ -439,15 +443,20 @@ private void pushRun(int runBase, int runLen) {
      * This method is called each time a new run is pushed onto the stack,
      * so the invariants are guaranteed to hold for i < stackSize upon
      * entry to the method.
+     *
+     * Thanks to Stijn de Gouw, Jurriaan Rot, Frank S. de Boer,
+     * Richard Bubel and Reiner Hahnle, this is fixed with respect to
+     * the analysis in "On the Worst-Case Complexity of TimSort" by
+     * Nicolas Auger, Vincent Jug, Cyril Nicaud, and Carine Pivoteau.
      */
     private void mergeCollapse() {
       while (stackSize > 1) {
         int n = stackSize - 2;
-        if ( (n >= 1 && runLen[n-1] <= runLen[n] + runLen[n+1])
-          || (n >= 2 && runLen[n-2] <= runLen[n] + runLen[n-1])) {
+        if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1] ||
 
 Review comment:
   I took the code from here: http://hg.openjdk.java.net/jdk/jdk11/file/1ddf9a99e4ad/src/java.base/share/classes/java/util/TimSort.java#l441

----------------------------------------------------------------
This is an automated message from the Apache Git Service.
To respond to the message, please log on GitHub and use the
URL above to go to the specific comment.
 
For queries about this service, please contact Infrastructure at:
users@infra.apache.org


With regards,
Apache Git Services

---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org