QuickSort { public static <E extends Comparable<E>> void quickSort(List<E> array) { if (array.isEmpty()) { return; } recursiveQuickSort(array, 0, array.size() - 1); }  static void quickSort(List<E> array); static void recursiveQuickSort(List<E> array, int startIdx,
      int endIdx); static int partition(List<E> array, int left, int right);  }
@Test public void testQuickSort() throws Exception { for (ImmutableList<Long> data : testdata) { List<Long> array = new ArrayList<Long>(data); QuickSort.quickSort(array); assertTrue(Ordering.natural().isOrdered(array)); } }
@Test public void testLargeQuickSort() throws Exception { final int size = 4000000; final Random r = new Random(size); ArrayList<LongPoint> list = new ArrayList<LongPoint>(size); for (int i = 0; i < size; i++) { list.add(new LongPoint(r.nextLong(), r.nextLong())); } assertFalse(Ordering.natural().isOrdered(list)); QuickSort.quickSort(list); assertTrue(Ordering.natural().isOrdered(list)); QuickSort.quickSort(list); assertTrue(Ordering.natural().isOrdered(list)); }
@Test public void testInplaceQuickSort() throws Exception { for (ImmutableList<Long> data : testdata) { InplaceList<Long> array = new UnsafeArrayList<Long>(Long.class, data); InplaceQuickSort.quickSort(array); assertTrue(Ordering.natural().isOrdered(array)); } }