Home



2020/01 - DS&A #9: Merge Sort (And a happy new year!)

Howdy folks!

Happy new year! What better way to kick off the new year than learning about (Or getting a refresher on) the Merge Sort algorithm, our first divide and conquer algorithm. The merge sort works by splitting up the array to be sorted in halves iteratively until it reaches the point that each element is contained within it's own array. It then reconstructs the original array step-by-step (Doubling each of the single-element arrays, as opposed to the halving we previously performed) sorting the array at each reconstruction, until the array is both whole again and sorted!

 

public class MergeSort {

    int[] valuesToSort;
    
    public MergeSort(int size) {
        valuesToSort = new int[size];
    }
    
    //Test odd-numbered capacity arrays    
    public static void main(String[] args) {
         
        MergeSort mergeSort = new MergeSort(args.length);
        
        for(int i = 0 ; i < args.length; i++) {
            mergeSort.valuesToSort[i] = Integer.valueOf(args[i]);
            System.out.print(mergeSort.valuesToSort[i]+",");
        }
        
        System.out.println("");
        System.out.println("***");
        int[] sortedFinish = mergeSort.recursivelySplit(mergeSort.valuesToSort) ;
            
        System.out.println("Sorted");
        for(int i = 0 ; i < sortedFinish.length; i++) {
            System.out.print(sortedFinish[i]+",");
        }
    }

Yet again, our familiar boilercode code makes an appearanc above. This wouldn't happen in Kotlin*.

 


    public int[] recursivelySplit(int[] currentArrayToSplit) {
        
        System.out.println("Splitting" + currentArrayToSplit);
        
        if(currentArrayToSplit.length > 1) {
            int[] leftSplit = Arrays.copyOfRange(currentArrayToSplit, 0, currentArrayToSplit.length/2);
            int[] rightSplit = Arrays.copyOfRange(currentArrayToSplit, currentArrayToSplit.length/2, currentArrayToSplit.length);
            int[] leftSplitResults = recursivelySplit(leftSplit);
            int[] rightSplitResults = recursivelySplit(rightSplit);
            int[] sortedArray = rejoinArrays(leftSplitResults,rightSplitResults);
            Arrays.sort(sortedArray);
            
            return sortedArray;
        }    
        else {
            return currentArrayToSplit;        
        }
    }

The above recursively splits the unsorted array into its constituent parts, which are enclosed in arrays. It's keeps doing so until it coannot split anymroe (at leftSplitResults and rightSplitResults instatiation). Because we're running this algorithm recursively, the program will then call rejoinArrays and Arrays.sort on each of the splitted arrays from the smallest representation of the elements/arrays until they eventually join together back into the original (and now sorted) array.

 


    public int[] rejoinArrays(int[] leftSplitResults, int[] rightSplitResults) {
        
        System.out.println("Adding " + leftSplitResults.length + " with " + rightSplitResults.length);
        int[] sortedSplitResults = new int[leftSplitResults.length + rightSplitResults.length];
        
        int t = 0;
        for(int i = 0; i <leftSplitResults.length; i++, t++) {
            sortedSplitResults[t] = leftSplitResults[i];
            
        }
        
        for(int i = 0; i <rightSplitResults.length; i++, t++) {
            sortedSplitResults[t] = rightSplitResults[i];
            
        }
        
        System.out.println("Result: "  + sortedSplitResults.length);
        
        return sortedSplitResults;

    }

}

The above is just another convenience method to deal with merging the arrays back together, so nothing particularly complex.

The merge sort is another fairly easy to understand algorithm, the first of our divide and conquer algorithms in this series. Hopefully you enjoyed this!

Good luck!

Marc

 

*Or maybe it would, I've never actually touched Kotlin. I just assume that most programming languages newer than Java have less boilerplate and am usually right.