Friday, 21 February 2014

Merge Sort in java

Background

 Mergesort is a divide and conquer algorithm that was invented by John von Neumann in 1945.

Conceptually it works as follows - 

  1. Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).
  2. Repeatedly merge sublists to produce new sorted sublists until there is only 1 sublist remaining. This will be the sorted list.

Code :

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * User: aniket
 * Date: 12/2/14
 * Time: 11:24 AM
 */
public class MergeSort {

    public void sort(int[] array) {
        mergeSort(array,0,array.length-1);

    }

    private void mergeSort(int[] array, int start, int end){

        if(start == end){
            return;
        }
        int mid = (start + end)/2;
        mergeSort(array, start, mid);
        mergeSort(array, mid+1, end);
        merge(array,start,mid,end);

    }

    private void merge(int[] array, int start, int mid, int end){

        int[] leftArray = Arrays.copyOfRange(array,start,mid+1);
        int[] rightArray = Arrays.copyOfRange(array,mid+1,end+1);

        int i = 0;
        int j = 0;

        int counter = start;

        while(i<leftArray.length && j<rightArray.length){
            if(leftArray[i] < rightArray[j]){
                array[counter] = leftArray[i];
                i++;
            }
            else {
                array[counter] = rightArray[j];
                j++;
            }
            counter++;
        }

        if(i == leftArray.length){
            while(j != rightArray.length){
                array[counter] = rightArray[j];
                j++;
                counter++;
            }
        }
        else{//j == rightArray.length
            while(i != leftArray.length){
                array[counter] = leftArray[i];
                i++;
                counter++;
            }

        }

    }

    public static void main(String args[]){

        int[] array = new int[]{2,7,5,9,4,7,1,0};
        System.out.println("Array Before Sort : " + Arrays.toString(array));
        new MergeSort().sort(array);
        System.out.println("Array after Sort : " + Arrays.toString(array));

    }

}

Output :

Array Before Sort : [2, 7, 5, 9, 4, 7, 1, 0]
Array after Sort : [0, 1, 2, 4, 5, 7, 7, 9]


Complexity

In sorting n objects, merge sort has an average and worst-case performance of O(n log n).

You can visualize it with following diagram -



Handling very large data

If the data set is very large (large that what can fit into RAM/main memory) then above approach will not work. In that case you need to do what is popularly know as - 
External merge sort is one such external sorting algorithm 
  • Sort chunks that each fit in RAM, then merges the sorted chunks together.
  • First divide the file into runs such that the size of a run is small enough to fit into main memory. Then sort each run in main memory using merge sort sorting algorithm.  
  • Finally merge the resulting runs together into successively bigger runs, until the file is sorted.
You can use following approach  to sort sorted runs -

Related Links

No comments:

Post a Comment

t> UA-39527780-1 back to top