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

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

srowen 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_r259010858
 
 

 ##########
 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:
   Looks good. TIL that `&&` has higher precedence that `||` so this doesn't change things. Actually the whole change on this line doesn't cause any actual change, which is good; aligning the implementation exactly is useful though.

----------------------------------------------------------------
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