Merge sort is a divide-and-conquer algorithm for sorting which has a time complexity of
O(n log n). It goes as follows given a sequence
1. Base case: If the sequence has a single element or no elements, it is sorted and we're done.
2. Divide step: Split the sequence in the middle, obtaining subsequences
3. Recurse step: Apply merge sort to each of the subsequences
B, which will now be sorted.
4. Merge step: Take the smallest element between the sorted
B subsequences by checking the next element of each from the start. If there are no more elements on either
B, take all the remaining elements of the other. Repeat this step until a sorted sequence is built with all elements of
B, which will be the sorted sequence
# NOTE: assuming both "a" and "b" are sorted sequences. # "c" acts as the accumulator for the resulting merged sequence. def merge_sorted_sequences(a, b, c=): # if either sequence is empty, return the other (base case) if len(a) == 0: return c + b if len(b) == 0: return c + a # take the smallest element of either "a" or "b" and build # up the resulting sorted sequence "c" if a <= b: return merge_sorted_sequences(a[1:], b, c + [a]) else: return merge_sorted_sequences(a, b[1:], c + [b]) def merge_sort(arr): if len(arr) <= 1: return arr # base case m = len(arr) // 2 # midpoint of "arr" p, q = arr[:m], arr[m:] # divide step a, b = merge_sort(p), merge_sort(q) # recursion step return merge_sorted_sequences(a, b) # conquer step
- “Introduction to Algorithms” by Thomas H. Cormen et al (2022).