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.


  1. If the list is of length 0 or 1, then it is already sorted. Otherwise:
  2. Divide the list into two sub-lists of about half of the size
  3. Sort each sub-list recursively
  4. 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]
               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