Merge sort

1.Merge sort

• This follow divide and conquer approach to create smaller sub-problems

  • A list is broken down into smaller and smaller parts recursively

• Then merge the sorted lists together to get the fully sorted list

2.Divide and Conquer

• A classic recursion based algorithm, divide till the problem is so small as to be trivial

  • Solve for the trivial case and then build up the complete solution as recursion unwinds

3.Code

1. The "split" method to split the list into 2 sub-lists

2. The "merge" method to merge 2 sorted lists into sorted list

3. The "mergeSort" method which does the final recursive sort

• Split method (take Θ (n1 + n2) = Θ (n) time )

  • The two lists for the first and second halves have been setup and split simply copies the elements from the first list over

  • The first half holds everything up to the mid-point

  • The second half holds reminder of the elements

public static void split(int[] listSort, int[] listFirstHalf, int[] listSecondHalf) {
    int index = 0;
    int secondHalfStrartIndex = listFirstHalf.length;
    for (int element: listToSort) {
        if ( inex < secondHalfStrartIndex) {
            listFirstHalf[index] = listSort[index];
        } else {
            listSecondHalf[index - secondHalfStrartIndex] = listSort[index];
        }
        index++;
    }
}

• Merge method (take Θ (n) time )

  • Set up indices into the final merged list and the two halves which are to be merged together.

  • Compare the element at the current index of each of the lists and choose the smaller one to go into the final list

  • Copy over the remaining elements left in either one of the lists

public static void merge(int[] listSort, int[] listFirstHalf, int[] listSecondHalf) {
    int mergeIndex = 0;
    int firstHalfIndex = 0;
    int secondHalfIndex = 0;
    
    while (firstHalfIndex < listFirstHalf.length &&
           secondHalfIndex < listSecondHalf.length){
           if (listFirstHalf[firstHalfIndex] < listSecondHalf[secondHalfIndex]) {
                  listSort[mergeIndex] = listFirstHalf[firstHalfIndex];
                  firstHalfIndex++;
           } else if (secondHalfIndex < listSecondHalf.length) {
                  listSort[mergeIndex] = listFirstHalf[secondHalfIndex];
                  secondHalfIndex++;
           }
           mergeIndex++;
    }
    
    if (firstHalfIndex < listFirstHalf.length) {
           while (mergeIndex < listToSort.length) {
                  listSort[mergeIndex] = listFirstHalf[firstHalfIndex++];
           }
    }
   
    if (secondHalfIndex < listSecondHalf.length) {
           while (mergeIndex < listToSort.length) {
                  listSort[mergeIndex] = listFirstHalf[secondHalfIndex++];
           }
    }
}

• MergeSort

public static void mergeSort(int[] listSort) {
    //A list of length 1 is a sorted list! 
    //This is the base case of recursion
    if (listSort.length == 1) {
        return;
    }
    
    //Get the mid-point at which to split the list
    int midIndex = listSort.length/2 + listSort.length%2;
    int[] listFirstHalf = new int[midIndex];
    int[] listSecondHalf = new int[listSort.length - midIndex];
    split(listSort, listFirstHalf, listSecondHalf);
    
    //Recursive call, merge sort the two smaller sub-lists created
    mergeSort(listFirstHalf);
    mergeSort(listSecondHalf);
    
    //Merge the sorted list to get the original list in sorted order
    merge(listSort, listFirstHalf, listSecondHalf);
    print(listSort);
}

4.Complexity

• The complexity of Merge sort is O(NLogN)

• The algorithm is not adaptive

• It takes O(N) extra space when we use arrays (all the smaller lists we create in the divide phase)

• It is a stable sort

• Running time T(n) of merge sort:

T(n) = 
Θ(1)       if n = 1
2T(n/2) + Θ(n)    if n > 1