FastMergeSort


1   // Copyright (c) 2003-2007, Jodd Team (jodd.sf.net). All Rights Reserved.
2   
3   package jodd.util.sort;
4   
5   import java.util.Comparator  ;
6   
7   import jodd.util.ComparableComparator;
8   
9   /**
10   * Faster merge sort. When original JDK routine runs 5s for sorting
11   * 1 milion objects this one runs for 3.5s.
12   */
13  public class FastMergeSort implements Sorter {
14  
15      private void mergeSort(Object   src[], Object   dest[], int low, int high, int off, Comparator   c) {
16          int length = high - low;
17  
18          // use insertion sort on smallest arrays
19          if (length < 7) {
20              for (int i = low; i < high; i++)
21                  for (int j = i; j > low && c.compare(dest[j - 1], dest[j]) > 0; j--) {
22                      Object   temp = src[j]; src[j] = src[j-1]; src[j-1] = temp;
23                  }
24              return;
25          }
26  
27          // recursively sort halves of dest into src
28          int destLow = low;
29          int destHigh = high;
30          low += off;
31          high += off;
32          int mid = (low + high) >> 1;
33          mergeSort(dest, src, low, mid, -off, c);
34          mergeSort(dest, src, mid, high, -off, c);
35  
36          // is list already sorted?
37          if (c.compare(src[mid - 1], src[mid]) <= 0) {
38              System.arraycopy(src, low, dest, destLow, length);
39              return;
40          }
41  
42          // merge sorted halves from src into dest
43          for (int i = destLow, p = low, q = mid; i < destHigh; i++) {
44              if (q >= high || p < mid && c.compare(src[p], src[q]) <= 0) {
45                  dest[i] = src[p++];
46              } else {
47                  dest[i] = src[q++];
48              }
49          }
50      }
51  
52      public void sort(Object  [] a, Comparator   c) {
53          Object   aux[] = (Object  [])a.clone(); 
54          mergeSort(aux, a, 0, a.length, 0, c); 
55      }
56  
57      public void sort(Comparable  [] a) {
58          Object   aux[] = (Object  [])a.clone(); 
59          mergeSort(aux, a, 0, a.length, 0, ComparableComparator.instance());
60      }
61  }
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags