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.