Prelude to the merge sort algorithm

  • The Merge Sort algorithm is one of the fastest sorting algorithms in Computer Science

  • It is a recursive algorithm

  • I will introduce the Merge Sort algorithm using the following simpler non-recursive sorting algorithm: 

      Sorting an array a[ ] of n elements:

     1. split the array a[ ] into 2 halves:

           an array left[ ]  containing a[0] .. a[n/2]
	   an array right[ ] containing a[n/2 + 1] .. a[n-1]

     2. Sort both halves of the arrays (left[ ] and right[ ])
        using Insertion Sort

     3. Merge the sorted arrays into the final sorted array

  • Later, I will replace the Insertion Sort with a recursive call to Merge Sort

Prelude to the merge sort algorithm

  • How the Merge Sort algorithm works: 

     Sort:       [6.4, 3.5, 7.5, 2.5, 8.9, 4.2, 9.2, 1.1]
                    /                    \
		   /  split into 2 halves \
		  /                        \
        [6.4, 3.5, 7.5, 2.5]        [8.9, 4.2, 9.2, 1.1]
                  |                         |
		  |     Sort each half      | (E.g.: use insertionSort) 
		  V                         V
        [2.5, 3.5, 6.4, 7.5]        [1.1, 4.2, 8.9, 9.2]
                  \                        /
		   \  Merge sorted halves /   (Use merge( ) !)
		    \                    /
             [1.1, 2.5, 3.5, 4.2, 6.4, 7.5, 8.9, 9.2]

     

Prelude to the merge sort algorithm

  • How the Merge Sort algorithm works: 

     Sort:       [6.4, 3.5, 7.5, 2.5, 8.9, 4.2, 9.2, 1.1]
                    /                    \
		   /  split into 2 halves \
		  /                        \
        [6.4, 3.5, 7.5, 2.5]        [8.9, 4.2, 9.2, 1.1] 
                  |                         |
		  |     Sort each half      | (E.g.: use insertionSort) 
		  V                         V
        [2.5, 3.5, 6.4, 7.5]        [1.1, 4.2, 8.9, 9.2]
                  \                        /
		   \  Merge sorted halves /   (Use merge( ) !)
		    \                    /
             [1.1, 2.5, 3.5, 4.2, 6.4, 7.5, 8.9, 9.2]

    (1) Split the input array into 2 equal halves

Prelude to the merge sort algorithm

  • How the Merge Sort algorithm works: 

     Sort:       [6.4, 3.5, 7.5, 2.5, 8.9, 4.2, 9.2, 1.1]
                    /                    \
		   /  split into 2 halves \
		  /                        \
        [6.4, 3.5, 7.5, 2.5]        [8.9, 4.2, 9.2, 1.1] 
                  |                         |
		  |     Sort each half      | (E.g.: use insertionSort) 
		  V                         V
        [2.5, 3.5, 6.4, 7.5]        [1.1, 4.2, 8.9, 9.2]
                  \                        /
		   \  Merge sorted halves /   (Use merge( ) !)
		    \                    /
             [1.1, 2.5, 3.5, 4.2, 6.4, 7.5, 8.9, 9.2]

    (2) Sort each array halves   --   we can use any sorting algorithm for this step

Prelude to the merge sort algorithm

  • How the Merge Sort algorithm works: 

     Sort:       [6.4, 3.5, 7.5, 2.5, 8.9, 4.2, 9.2, 1.1]
                    /                    \
		   /  split into 2 halves \
		  /                        \
        [6.4, 3.5, 7.5, 2.5]        [8.9, 4.2, 9.2, 1.1] 
                  |                         |
		  |     Sort each half      | (E.g.: use insertionSort) 
		  V                         V
        [2.5, 3.5, 6.4, 7.5]        [1.1, 4.2, 8.9, 9.2]
                  \                        /
		   \  Merge sorted halves /   (Use merge( ) !)
		    \                    /
             [1.1, 2.5, 3.5, 4.2, 6.4, 7.5, 8.9, 9.2]

    (3) Merge the 2 sorted (half) arrays to obtain the sorted (result) array

A simplied merge sort algorithm

Let's write this sorting algorithm: 

    public static void mergeSort(double[] a)  // Not the actual mergeSort algorithm  
    {
	int middle     = a.length/2;
	double[] left  = new double[a.length/2];            // left half
        double[] right = new double[a.length - a.length/2]; // right half
     
	if ( a.length == 1 )
	    return;     // No need to sort an array of 1 element...

	// Split:       a[0 ..... middle-1]  a[middle .... a.length-1]
        //	        left[0 .. middle-1]  right[0 ... a.length-1-middle]
	for ( int i = 0; i < middle; i++ )
	   left[i] = a[i];

	for ( int i = 0; i < a.length-middle; i++ )
	   right[i] = a[i+middle];

	// Sort both halves - you can any sort algorithm !
	BubbleSort.sort( left );
	BubbleSort.sort( right );

	/* Merge both sorted arrays 
	merge( a, left, right );   // We have discussed merge() already...   
    }

A simplied merge sort algorithm

Define 2 arrays to store the left half and the right half of the input array: 

    public static void mergeSort(double[] a)  // Not the actual mergeSort algorithm  
    {
	int middle     = a.length/2;
	double[] left  = new double[a.length/2];            // left half
        double[] right = new double[a.length - a.length/2]; // right half
 
        // Define variables to split input array into 2 halves    
	if ( a.length == 1 )
	    return;     // No need to sort an array of 1 element...

	// Split:       a[0 ..... middle-1]  a[middle .... a.length-1]
        //	        left[0 .. middle-1]  right[0 ... a.length-1-middle]
	for ( int i = 0; i < middle; i++ )
	   left[i] = a[i];

	for ( int i = 0; i < a.length-middle; i++ )
	   right[i] = a[i+middle];

	// Sort both halves - you can any sort algorithm !
	BubbleSort.sort( left );
	BubbleSort.sort( right );
	/* Merge both sorted arrays 
	merge( a, left, right );   // We have discussed merge() already...   
    }

A simplied merge sort algorithm

 If  the input array only contains 1 element, we do not need to sort it (because it's already sorted): 

    public static void mergeSort(double[] a)  // Not the actual mergeSort algorithm  
    {
	int middle     = a.length/2;
	double[] left  = new double[a.length/2];            // left half
        double[] right = new double[a.length - a.length/2]; // right half
 
	if ( a.length == 1 )   // Base case
	    return;            // No need to sort an array of 1 element...

	// Split:       a[0 ..... middle-1]  a[middle .... a.length-1]
        //	        left[0 .. middle-1]  right[0 ... a.length-1-middle]
	for ( int i = 0; i < middle; i++ )
	   left[i] = a[i];

	for ( int i = 0; i < a.length-middle; i++ )
	   right[i] = a[i+middle];

	// Sort both halves - you can any sort algorithm !
	BubbleSort.sort( left );
	BubbleSort.sort( right );

	/* Merge both sorted arrays 
	merge( a, left, right );   // We have discussed merge() already...   
    }

A simplied merge sort algorithm

For arrays with > 1 element, we split the input array into 2 equal halves: 

    public static void mergeSort(double[] a)  // Not the actual mergeSort algorithm  
    {
	int middle     = a.length/2;
	double[] left  = new double[a.length/2];            // left half
        double[] right = new double[a.length - a.length/2]; // right half
 
	if ( a.length == 1 )   // Base case
	    return;            // No need to sort an array of 1 element...

	// Split:       a[0 ..... middle-1]  a[middle .... a.length-1]      
        //	as:     left[0 .. middle-1]  right[0 ... a.length-1-middle] 
	for ( int i = 0; i < middle; i++ )
	   left[i] = a[i];

	for ( int i = 0; i < a.length-middle; i++ )
	   right[i] = a[i+middle];

	// Sort both halves - you can any sort algorithm !
	BubbleSort.sort( left );
	BubbleSort.sort( right );

	/* Merge both sorted arrays 
	merge( a, left, right );   // We have discussed merge() already...   
    }

A simplied merge sort algorithm

We sort both halves of the arrays   --   we use insertionSort( ), but any sort method can be used: 

    public static void mergeSort(double[] a)  // Not the actual mergeSort algorithm  
    {
	int middle     = a.length/2;
	double[] left  = new double[a.length/2];            // left half
        double[] right = new double[a.length - a.length/2]; // right half
 
	if ( a.length == 1 )   // Base case
	    return;            // No need to sort an array of 1 element...

	// Split:       a[0 ..... middle-1]  a[middle .... a.length-1]      
        //	as:     left[0 .. middle-1]  right[0 ... a.length-1-middle] 
	for ( int i = 0; i < middle; i++ )
	   left[i] = a[i];

	for ( int i = 0; i < a.length-middle; i++ )
	   right[i] = a[i+middle];

	// Sort both halves - you can use any sort algorithm !
	insertionSort( left );
	insertionSort( right );

	/* Merge both sorted arrays 
	merge( a, left, right );   // We have discussed merge() already...   
    }

A simplied merge sort algorithm

Finally, we use the merge( ) method to merge the 2 sorted array to obtain one sorted output array: 

    public static void mergeSort(double[] a)  // Not the actual mergeSort algorithm  
    {
	int middle     = a.length/2;
	double[] left  = new double[a.length/2];            // left half
        double[] right = new double[a.length - a.length/2]; // right half
 
	if ( a.length == 1 )   // Base case
	    return;            // No need to sort an array of 1 element...

	// Split:       a[0 ..... middle-1]  a[middle .... a.length-1]      
        //	as:     left[0 .. middle-1]  right[0 ... a.length-1-middle] 
	for ( int i = 0; i < middle; i++ )
	   left[i] = a[i];

	for ( int i = 0; i < a.length-middle; i++ )
	   right[i] = a[i+middle];

	// Sort both halves - you can use any sort algorithm !
	insertionSort( left );
	insertionSort( right );

	// Merge both sorted arrays 
	merge( a, left, right );   // We have discussed merge() already...   
    }

Test program for mergeSort 

    public static void main(String[] args)
    {
        double[] myList = {5.6,  7.8,  2.4,  3.3};
        
        for (int i = 0; i < myList.length; i++)
            System.out.print( myList[i] + "  ");
        System.out.println();
        
        mergeSort( myList );
        
        for (int i = 0; i < myList.length; i++)
            System.out.print( myList[i] + "  ");
        System.out.println();
    }

DEMO: demo/08-array/12-sorting/PreMergeSort.java

Note:   the merge( ) and insertionSort( ) methods have been discussed previously and must be included in the program

The official merge sort algorithm 

    public static void mergeSort(double[] a)  // Not the actual mergeSort algorithm  
    {
	int middle     = a.length/2;
	double[] left  = new double[a.length/2];            // left half
        double[] right = new double[a.length - a.length/2]; // right half
 
	if ( a.length == 1 )   // Base case
	    return;            // No need to sort an array of 1 element...

	// Split:       a[0 ..... middle-1]  a[middle .... a.length-1]      
        //	as:     left[0 .. middle-1]  right[0 ... a.length-1-middle] 
	for ( int i = 0; i < middle; i++ )
	   left[i] = a[i];

	for ( int i = 0; i < a.length-middle; i++ )
	   right[i] = a[i+middle];

	// Sort both halves - we can use any sort algorithm here:
	insertionSort( left );  // I used insertionSort( ) to make it simple
	insertionSort( right ); // to explain what we want to achieve

	// Merge both sorted arrays 
	merge( a, left, right );   // We have discussed merge() already...   
    }

The official merge sort algorithm 

    public static void mergeSort(double[] a)  // The actual mergeSort algorithm  
    {
	int middle     = a.length/2;
	double[] left  = new double[a.length/2];            // left half
        double[] right = new double[a.length - a.length/2]; // right half
 
	if ( a.length == 1 )   // Base case
	    return;            // No need to sort an array of 1 element...

	// Split:       a[0 ..... middle-1]  a[middle .... a.length-1]      
        //	as:     left[0 .. middle-1]  right[0 ... a.length-1-middle] 
	for ( int i = 0; i < middle; i++ )
	   left[i] = a[i];

	for ( int i = 0; i < a.length-middle; i++ )
	   right[i] = a[i+middle];

	// Sort both halves - the mergeSort algorithm is recursive !
	mergeSort( left );      // We use mergeSort itself here !
	mergeSort( right );     // We use mergeSort again here !

	// Merge both sorted arrays 
	merge( a, left, right );   // We have discussed merge() already...   
    }

DEMO: demo/08-array/12-sorting/MergeSort.java

How the mergeSort algorithm works

Consider the mergeSort( ) algorithm on the following input: 

 mergeSort(A[0-7])

How the mergeSort algorithm works

mergeSort( ) first split the input array into 2 halves: 

 mergeSort(A[0-7])

How the mergeSort algorithm works

mergeSort( ) then recurses and sort the first half: 

 mergeSort(A[0-7]) --> mergeSort(A[0-3])

How the mergeSort algorithm works

The new mergeSort( ) first split the input array into 2 halves: 

 mergeSort(A[0-7]) --> mergeSort(A[0-3])

How the mergeSort algorithm works

This mergeSort( ) then recurses and sort the first half: 

 mergeSort(A[0-7]) --> mergeSort(A[0-3]) --> mergeSort(A[0-1])

How the mergeSort algorithm works

The new mergeSort( ) first split the input array into 2 halves: 

 mergeSort(A[0-7]) --> mergeSort(A[0-3]) --> mergeSort(A[0-1])

How the mergeSort algorithm works

This mergeSort( ) then recurses and sort the first half: 

 mergeSort(A[0-7]) --> mergeSort(A[0-3]) --> mergeSort(A[0-1]) --> mergeSort(A[0-0])

How the mergeSort algorithm works

The input array consists of 1 element (= base case) and mergeSort( ) returns 

 mergeSort(A[0-7]) --> mergeSort(A[0-3]) --> mergeSort(A[0-1]) <== mergeSort(A[0-0])

How the mergeSort algorithm works

The mergeSort( ) then recurses and sort the 2nd half: 

 mergeSort(A[0-7]) --> mergeSort(A[0-3]) --> mergeSort(A[0-1]) --> mergeSort(A[1-1])

How the mergeSort algorithm works

The input array consists of 1 element (= base case) and mergeSort( ) returns 

 mergeSort(A[0-7]) --> mergeSort(A[0-3]) --> mergeSort(A[0-1]) <== mergeSort(A[1-1])

How the mergeSort algorithm works

Merge sort will finally merge the 2 sorted arrays and return to the previous mergeSort( ): 

 mergeSort(A[0-7]) --> mergeSort(A[0-3]) <== mergeSort(A[0-1])

How the mergeSort algorithm works

This mergeSort( ) then recurses and sort the 2nd half: 

 mergeSort(A[0-7]) --> mergeSort(A[0-3]) --> mergeSort(A[2-3])

How the mergeSort algorithm works

The new mergeSort( ) will repeat the previously shown steps (omitted) - the result is sorting the input array: 

 mergeSort(A[0-7]) --> mergeSort(A[0-3]) <== mergeSort(A[2-3])

How the mergeSort algorithm works

The 2nd level mergeSort( ) will merge the 2 sorted arrays and ... 

 mergeSort(A[0-7]) --> mergeSort(A[0-3]): merge(A[0-1], A[2-3])

How the mergeSort algorithm works

The 2nd level mergeSort( ) will merge the 2 sorted arrays and return to the top level mergeSort( ): 

 mergeSort(A[0-7]) <== mergeSort(A[0-3])

How the mergeSort algorithm works

The top level mergeSort( ) then recurses and sort the 2nd half: 

 mergeSort(A[0-7]) --> mergeSort(A[4-7])

How the mergeSort algorithm works

The new mergeSort( ) will repeat the previously shown steps ( omitted) - the result is sorting the input array: 

 mergeSort(A[0-7]) <== mergeSort(A[4-7])

How the mergeSort algorithm works

Finally, the top level mergeSort( ) will merge the sorted arrays: 

 mergeSort(A[0-7]): merge(A[0-3], A[4-7])

How the mergeSort algorithm works

Final result: 

 mergeSort(A[0-7]): return (array is sorted !)