Merge Sort Algorithm - Java Applet Visualization

The gadget spec URL could not be found

 An example of Merge Sort : Scroll down to see the Java Applet Visualization at the bottom of the page.



Merge Sort :

This is a "divide and conquer" technique . 
The array is split into two halves . Both the halves are sorted independently . 
And then they are merged . This idea is recursively applied to the two sub-arrays
as well .

mergeSort(startIndex , endIndex)
{
halfMark = startIndex + (endIndex-startIndex)/2 
mergeSort(startIndex,halfMark)
mergeSort(halfMark+1,startIndex)
merge(startIndex,halfMark,endIndex);
}

// Merge the two sorted halves in linear time 

void merge(int lo, int m, int hi)
{
    int i, j, k;
    int b[] = new int[arraySize];
    for (i=lo; i<=hi; i++)
        b[i]=array[i];
    i=lo; j=m+1; k=lo;
    while (i<=m && j<=hi)
        if (b[i]<=b[j])
            array[k++]=b[i++];
        else
            array[k++]=b[j++];
    while (i<=m)
        array[k++]=b[i++];
}

"Start" the visualization :

Comments