Merge Sort

Part:   1  2 

This chapter helps you to understand:

• Basic Idea
• Java Implementation
• Performance
• Improvements

Basic Idea

The basic idea of Merge Sort is to:

1. Divide the data elements into two sections with equal number of elements.

2. Sort the two sections separately.

3. Merge the two sorted sections into a single sorted collection.

Obviously, this is a recursive idea, where a problem is divided into smaller problems. And the division will be repeated to make the smaller problems even smaller, until they are smaller enough so that the solutions are obvious.

Java Implementation

Here is my Java implementation of Merge Sort algorithm:

/**
 * 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 mergeSort(Object[] a, int fromIndex, 
      int toIndex) {
      Object[] b = new Object[toIndex];
      for (int i=fromIndex; i<toIndex; i++) {
         b[i] = a[i];
      }
      mergeSortInternal(b, a, fromIndex, toIndex);
   }
   private static void mergeSortInternal(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 iMiddle = (toIndex-fromIndex)/2 + fromIndex;
         mergeSortInternal(b,a,fromIndex,iMiddle);
         mergeSortInternal(b,a,iMiddle,toIndex);
         int iLeft = fromIndex;
         int iRight = iMiddle;
         int i = fromIndex;
         while (iLeft<iMiddle && iRight<toIndex) {
            if (((Comparable)a[iLeft]).compareTo(a[iRight])>0) {
               b[i] = a[iRight];
               iRight++;
            } else {
               b[i] = a[iLeft];
               iLeft++;
            }
            i++;
         }
         while (iLeft<iMiddle) {
            b[i] = a[iLeft];
            iLeft++;
            i++;
         }
         while (iRight<toIndex) {
            b[i] = a[iRight];
            iRight++;
            i++;
         }
      }
   }
}

• Method mergeSort() is a wrapper of the real sorting method: mergeSortInternal().
• Array b[] is created to help merging the two sorted sections back into a single sorted collection.

Performance

Now let's see how it performs. I tried this implementation with my SortTest.java under JDK 1.3.1. Here are the results:

Array size: 10000
Average sorting time: 98 milliseconds
Number of tests: 1000
Performance: 9.8 O(N) nonaseconds
Performance: 0.7375234893767539 O(N*Log2(N)) nonaseconds
Performance: 9.8E-4 O(N*N) nonaseconds

Array size: 20000
Average sorting time: 222 milliseconds
Number of tests: 1000
Performance: 11.1 O(N) nonaseconds
Performance: 0.7768913388743642 O(N*Log2(N)) nonaseconds
Performance: 5.55E-4 O(N*N) nonaseconds

Array size: 30000
Average sorting time: 336 milliseconds
Number of tests: 1000
Performance: 11.2 O(N) nonaseconds
Performance: 0.753058887534575 O(N*Log2(N)) nonaseconds
Performance: 3.733333333333333E-4 O(N*N) nonaseconds

The performance of this implementation is at the order of O(N*Log2(N)). But it is about 5 times slower than java.util.Arrays.sort().

(Continued on next part...)

Part:   1  2 

This site Web