Saturday, March 17, 2012

Merge Sort in Java

Dear reader,

Merge Sort is a divide and conquer algorithm. The sorting elements are stored in a collection. This 
collection is divided into two collections and these are again sorted via mergesort. Once the two 
collections are sorted then the result is combined.

Mergesort will take the middle of the collection and takes then the two collection for the next iteration 
of mergesort. In the merging part mergesort runs through the both collections and selects the lowest of 
the both to insert it into a new collection.

In comparison to quicksort the divide part is simple in mergesort while the merging take is complex. 
In addition quicksort can work "inline", e.g. it does not have to create a copy of the collection while 
mergesort requires a copy. 

Time efficiency:
Mergesort sorts in worst case in O(n log n) time. Due to the required copying of the collection, Mergesort is 
in the average case slower then Quicksort. 

===============MergeSort.java============
public class MergeSort {
    private int mArray[] = {13,4,70,12,9,4,99,120,1,3,10};
    private int[] tempArray;
    private int length;

    public void sort() {
        length = mArray.length;
        this.tempArray = new int[length];
        System.out.println("Array elements before Merge sorting:");
        for(int num:mArray)
            System.out.print(num+", ");
        mergesort(0, length - 1);
        System.out.println("\nArray elements After Merge sorting:");
        for(int num:mArray)
            System.out.print(num+", ");
    }
    public static void main(String a[]){
        new MergeSort().sort();
    }

    private void mergesort(int low, int high) {
        //Check if low is smaller then high, if not then the array is sorted
        if (low < high) {
            int middle = (low + high) / 2;
            //Sort the left side of the array
            mergesort(low, middle);
            //Sort the right side of the array
            mergesort(middle + 1, high);
            //Combine them both
            merge(low, middle, high);
        }
    }

    private void merge(int low, int middle, int high) {
        //Copy both parts into the helper array
        for (int i = low; i <= high; i++) {
            tempArray[i] = mArray[i];
        }
        int i = low;
        int j = middle + 1;
        int k = low;
        //Copy the smallest values from either the left or the right side back to the original array
        while (i <= middle && j <= high) {
            if (tempArray[i] <= tempArray[j]) {
                mArray[k] = tempArray[i];
                i++;
            } 
            else {
                mArray[k] = tempArray[j];
                j++;
            }
            k++;
        }
        //Copy the rest of the left side of the array into the target array
        while (i <= middle) {
            mArray[k] = tempArray[i];
            k++;
            i++;
        }
    }
}

//Output:
Array elements before Merge sorting:
13, 4, 70, 12, 9, 4, 99, 120, 1, 3, 10, 
Array elements After Merge sorting:
1, 3, 4, 4, 9, 10, 12, 13, 70, 99, 120, 

Other Sorting links can be found in below links: 
http://www.deepakmodi2006.blogspot.in/2012/03/quicksort-in-java.html
http://deepakmodi2006.blogspot.in/2012/03/sorting-in-java.html

===================END===================

No comments:

Post a Comment