Fix dual-pivot sort.

tests/corelib/src/SortTest.dart

Index: tests/corelib/src/SortTest.dart
diff --git a/tests/corelib/src/SortTest.dart b/tests/corelib/src/SortTest.dart
index 4b48592c8f37741fd8dd5544c27db9e98f1eb6a8..c9ea814f170e2daaa2b41c2e59102017ae105d96 100644
--- a/tests/corelib/src/SortTest.dart
+++ b/tests/corelib/src/SortTest.dart
@@ -7,18 +7,49 @@
 #import("dart:coreimpl");
 #source("SortHelper.dart");
 
-class SortTest {
-
-  static void testMain() {
-    var compare = (a, b) => a.compareTo(b);
-    var sort = (list) => DualPivotQuicksort.sort(list, compare);
-    new SortHelper(sort, compare).run();
-
-    compare = (a, b) => -a.compareTo(b);
-    new SortHelper(sort, compare).run();
+void checkListEquals(List expected, List actual) {
+  Expect.equals(expected.length, actual.length);
+  for (int i = 0; i < expected.length; i++) {
+    Expect.equals(expected[i], actual[i]);
   }
 }
 
 main() {
-  SortTest.testMain();
+  var compare = (a, b) => a.compareTo(b);
+  var sort = (list) => DualPivotQuicksort.sort(list, compare);
+  new SortHelper(sort, compare).run();
+
+  compare = (a, b) => -a.compareTo(b);
+  new SortHelper(sort, compare).run();
+
+  compare = (a, b) => a.compareTo(b);
+
+  // Pivot-canditate indices: 7, 15, 22, 29, 37
+  // Test dutch flag partitioning (canditates 2 and 4 are the same).
+  var list = [0, 0, 0, 0, 0, 0, 0, 0/**/, 0, 0, 0, 0, 0, 0, 0,
+              1/**/, 1, 1, 1, 1, 1, 1, 1/**/, 1, 1, 1, 1, 1, 1, 1/**/,
+              2, 2, 2, 2, 2, 2, 2, 2/**/, 2, 2, 2, 2, 2, 2, 2];
+  list.sort(compare);
+  checkListEquals(list, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+                         1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
+                         2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]);
+
+  list = [0, 0, 0, 0, 0, 0, 0, 1/**/, 0, 0, 0, 0, 0, 0, 0,
+          0/**/, 1, 1, 1, 1, 1, 1, 0/**/, 1, 1, 1, 1, 1, 1, 0/**/,
+          2/**/, 2, 2, 2, 2, 2, 2, 2/**/, 2, 2, 2, 2, 2, 2, 2];
+  list.sort(compare);
+  checkListEquals(list, [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+                         0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
+                         2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2]);
+
+  // Pivots: 1 and 8.
+  // The second partition will be big (more than 2/3 of the list), and an
+  // optimization kicks in that removes the pivots from the partition.
+  list = [0, 9, 0, 9, 3, 9, 0, 1/**/, 1, 0, 1, 9, 8, 2, 1,
+          1/**/, 4, 5, 2, 5, 0, 1, 8/**/, 8, 8, 5, 2, 2, 9, 8/**/,
+          8, 4, 4, 1, 5, 3, 2, 8/**/, 5, 1, 2, 8, 5, 6, 8];
+  list.sort(compare);
+  checkListEquals(list, [0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2,
+                         2, 2, 2, 2, 3, 3, 4, 4, 4, 5, 5, 5, 5, 5, 5,
+                         6, 8, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9]);
 }