diff options
| author | Evan Yu <ehotou@gmail.com> | 2015-02-28 18:55:34 -0800 |
|---|---|---|
| committer | Reynold Xin <rxin@databricks.com> | 2015-02-28 18:55:34 -0800 |
| commit | 643300a6e27dac3822f9a3ced0ad5fb3b4f2ad75 (patch) | |
| tree | 78c757c9102b668246d47c8f4797388596e082db /core/src/main/java | |
| parent | 86fcdaef62dbe624233e364ffe43fe3a1da893f0 (diff) | |
| download | spark-643300a6e27dac3822f9a3ced0ad5fb3b4f2ad75.tar.gz spark-643300a6e27dac3822f9a3ced0ad5fb3b4f2ad75.tar.bz2 spark-643300a6e27dac3822f9a3ced0ad5fb3b4f2ad75.zip | |
SPARK-5984: Fix TimSort bug causes ArrayOutOfBoundsException
Fix TimSort bug which causes a ArrayOutOfBoundsException.
Using the proposed fix here
http://envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/
Author: Evan Yu <ehotou@gmail.com>
Closes #4804 from hotou/SPARK-5984 and squashes the following commits:
3421b6c [Evan Yu] SPARK-5984: Add info to LICENSE
e61c6b8 [Evan Yu] SPARK-5984: Fix license and document
6ccc280 [Evan Yu] SPARK-5984: Add License header to file
e06c0d2 [Evan Yu] SPARK-5984: Add License header to file
4d95f75 [Evan Yu] SPARK-5984: Fix TimSort bug causes ArrayOutOfBoundsException
479a106 [Evan Yu] SPARK-5984: Fix TimSort bug causes ArrayOutOfBoundsException
Diffstat (limited to 'core/src/main/java')
| -rw-r--r-- | core/src/main/java/org/apache/spark/util/collection/TimSort.java | 9 |
1 files changed, 4 insertions, 5 deletions
diff --git a/core/src/main/java/org/apache/spark/util/collection/TimSort.java b/core/src/main/java/org/apache/spark/util/collection/TimSort.java index 409e1a41c5..a90cc0e761 100644 --- a/core/src/main/java/org/apache/spark/util/collection/TimSort.java +++ b/core/src/main/java/org/apache/spark/util/collection/TimSort.java @@ -425,15 +425,14 @@ class TimSort<K, Buffer> { private void mergeCollapse() { while (stackSize > 1) { int n = stackSize - 2; - if (n > 0 && runLen[n-1] <= runLen[n] + runLen[n+1]) { + if ( (n >= 1 && runLen[n-1] <= runLen[n] + runLen[n+1]) + || (n >= 2 && runLen[n-2] <= runLen[n] + runLen[n-1])) { if (runLen[n - 1] < runLen[n + 1]) n--; - mergeAt(n); - } else if (runLen[n] <= runLen[n + 1]) { - mergeAt(n); - } else { + } else if (runLen[n] > runLen[n + 1]) { break; // Invariant is established } + mergeAt(n); } } |