Merge Sort

Part:   1  2 

(Continued from previous part...)

Improvements

One way to improve the performance is to divid the data elements into 3 sections. Sort them separately, then merge them. Merging 3 sorted sections is more efficient than merging 2 sections. Here my improved implementation:

/**
 * HyArrays.java
 * This class contains sorting methods similar to java.util.Arrays.
 * All sorting methods should have a signiture of 
 * %Sort(Object[] a, int fromIndex, int toIndex)
 * where "fromIndex" is inclusive, and "toIndex" is exclusive.
 * Copyright (c) 1999 by Dr. Herong Yang
 */
public class HyArrays {
   public static void mergeSort3(Object[] a, int fromIndex, 
      int toIndex) {
      Object[] b = new Object[toIndex];
      for (int i=fromIndex; i<toIndex; i++) {
         b[i] = a[i];
      }
      mergeSortInternal3(b, a, fromIndex, toIndex);
   }
   private static void mergeSortInternal3(Object[] a, Object[] b, 
      int fromIndex, int toIndex) {
      if (toIndex-fromIndex<=1) {
         return;
      } else if (toIndex-fromIndex==2) {
         if (((Comparable)a[fromIndex]).compareTo(a[toIndex-1])>0) {
            b[toIndex-1] = a[fromIndex];
            b[fromIndex] = a[toIndex-1];
         }
      } else {
         int iLeft = (toIndex-fromIndex)/3 + fromIndex;
         int iRight = (toIndex-iLeft)/2 + iLeft;
         mergeSortInternal3(b,a,fromIndex,iLeft);
         mergeSortInternal3(b,a,iLeft,iRight);
         mergeSortInternal3(b,a,iRight,toIndex);
      	 int iFirst = fromIndex;
      	 int iSecond = iLeft;
      	 int iThird = iRight;
         int i = fromIndex;
         while (iFirst<iLeft && iSecond<iRight && iThird<toIndex) {
            if (((Comparable)a[iFirst]).compareTo(a[iSecond])<0) {
               if (((Comparable)a[iFirst]).compareTo(a[iThird])<0) {
                  b[i] = a[iFirst];
                  iFirst++;
               } else {
                  b[i] = a[iThird];
                  iThird++;
               }
            } else {
               if (((Comparable)a[iSecond]).compareTo(a[iThird])<0) {
                  b[i] = a[iSecond];
                  iSecond++;
               } else {
                  b[i] = a[iThird];
                  iThird++;
               }
            }
            i++;
         }
         while (iFirst<iLeft && iSecond<iRight) {
            if (((Comparable)a[iFirst]).compareTo(a[iSecond])<0) {
               b[i] = a[iFirst];
               iFirst++;
            } else {
               b[i] = a[iSecond];
               iSecond++;
            }
            i++;
         }
         while (iSecond<iRight && iThird<toIndex) {
            if (((Comparable)a[iSecond]).compareTo(a[iThird])<0) {
               b[i] = a[iSecond];
               iSecond++;
            } else {
               b[i] = a[iThird];
               iThird++;
            }
            i++;
         }
         while (iThird<toIndex && iFirst<iLeft) {
            if (((Comparable)a[iFirst]).compareTo(a[iThird])<0) {
               b[i] = a[iFirst];
               iFirst++;
            } else {
               b[i] = a[iThird];
               iThird++;
            }
            i++;
         }
         while (iFirst<iLeft) {
            b[i] = a[iFirst];
            iFirst++;
            i++;
         }
         while (iSecond<iRight) {
            b[i] = a[iSecond];
            iSecond++;
            i++;
         }
         while (iThird<toIndex) {
            b[i] = a[iThird];
            iThird++;
            i++;
         }
      }
   }
}

Performance was indeed improved:

Array size: 10000
Average sorting time: 69 milliseconds
Number of tests: 1000
Performance: 6.9 O(N) nonaseconds
Performance: 0.5192767425203676 O(N*Log2(N)) nonaseconds
Performance: 6.9E-4 O(N*N) nonaseconds

Array size: 20000
Average sorting time: 149 milliseconds
Number of tests: 1000
Performance: 7.45 O(N) nonaseconds
Performance: 0.5214270697850463 O(N*Log2(N)) nonaseconds
Performance: 3.725E-4 O(N*N) nonaseconds

Array size: 30000
Average sorting time: 241 milliseconds
Number of tests: 1000
Performance: 8.033333333333333 O(N) nonaseconds
Performance: 0.5401404520709302 O(N*Log2(N)) nonaseconds
Performance: 2.6777777777777775E-4 O(N*N) nonaseconds

Please also note that merge sort requires a working array to do the merge. Another direction of improving this implementation is to try to reduce or eliminate the working array.

Part:   1  2 

This site Web