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_r259005983
##########
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:
Are you sure about removing the parentheses? that changes the semantics, I
believe, to (((a and b) or c) and d) . What's the implementation you're copying
here, just to be sure?
----------------------------------------------------------------
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:
[email protected]
With regards,
Apache Git Services
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
