2.5 Merge Sort

Merge Sort is a comparison-based sorting algorithm by using Divide-and-Conquer. The key idea of Merge Sort is that, a shorter list takes fewer steps than a longer list, and also constructing a sorted list from two sorted lists takes lower time complexity than from two unsorted lists.

Algorithm

 If the list is of length 0 or 1, then it is already sorted. Otherwise: Divide the list into two sub-lists of about half of the size Sort each sub-list recursively Merge the two sub-lists into one sorted list

Time Complexity & Space Complexity
Consider the recurrence T(n) = 2T(n/2) + O(n) when assuming merging takes O(n), by the master theorem it will be seen that the time complexity is O(n log n)

Pseudo Code

 ```Function MergeSort( Array[1..n] )    If n <= 1        Report Array[1..n]    var leftSubArray = MergeSort( Array[1..n/2] )    var rightSubArray = MergeSort( Array[n/2+1..n] )    Report Merge( leftSubArray, rightSubArray ) Function Merge( left[1..m], right[1..n] )    var resultArray    while length(left) > 0 or length(right) > 0 then        If length(left) > 0 and length(right) > 0 then            If left[1] <= right[1] then                append left[1] to resultArray                left = left[2..m]            Else                append right[1] to resultArray                right = right[2..n]        Else if length(left) > 0 then            append left[1] to resultArray            left = left[2..m]        Else if length(right) > 0 then            append right[1] to resultArray            right = right[2..n]    end while    Report resultArray ```

 © The University of Hong Kong Algorithms Library - hkual@cs.hku.hk