Source

Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree

Sorting Problem

Input: a sequence of items that can be ordered (numbers, strings, dates). Output: a permutation with .

Divide and Conquer

Mergesort uses the divide and conquer idea, since a small array is easier to sort than a large one:

  • if the array has a single element, stop (it is already sorted)
  • divide: split the array into two nearly equal halves at
  • conquer: sort each half recursively with mergesort
  • combine: join the two sorted halves with the Merge Procedure

Code

def mergesort(A, i, j):
    if i == j:                     # one element, already sorted
        return
    m = (i + j) // 2               # divide into two nearly equal parts
    mergesort(A, i, m)             # sort left half
    mergesort(A, m + 1, j)         # sort right half
    merge(A, i, m, j)              # merge the sorted halves
 
A = [12, 30, 21, 8, 6, 9, 1, 7]
mergesort(A, 0, len(A) - 1)
print(A)                           # [1, 6, 7, 8, 9, 12, 21, 30]

Example with 8 Elements

The array is split down to single elements, then merged back pairwise: , , , , then and , then the final sorted array.

Complexity

Let be the number of operations for elements. Two half-size sorts plus a merge gives

Backward substitution with :

So in the best, average and worst case. The price is the extra arrays used in each merge.