Full merge sort

Recursive merge sort with O(n log n) complexity.

Full merge sort

Full merge sort combines split + recursion + merge. Base case: if the array has one element, it is already sorted, return it.

Otherwise, split in two, recursively sort each half, then merge. Each call halves the problem.

The result: a stable sort that always runs in O(n log n).

Stability

Merge sort is stable: equal-key elements keep their relative order. This is because during merge, when left[i] <= right[j], we take the left element first.

Stability matters when sorting objects by a key: a secondary order is preserved.

That is why merge sort is preferred in database sorts and external sorting.

Exercise Full merge sort

Write merge_sort(arr). Split, recursively sort, merge. Print [1, 2, 5, 8, 9] with print(merge_sort([5, 2, 8, 1, 9])).

Show example solution

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    result.extend(left[i:]); result.extend(right[j:])
    return result
def merge_sort(arr):
    # Split, sort, merge
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    return merge(merge_sort(arr[:mid]), merge_sort(arr[mid:]))
print(merge_sort([5, 2, 8, 1, 9]))

Test yourself

Full merge sort: match the terms

Base case

Single element
Split

Two halves
Merging

merge
Cost

O(n log n)
When does merge sort give O(n log n)?
- Only in the best case
- Only on sorted arrays
- Only in the worst case
- Always
Show answer

Always — Always
Base case
```
if len(arr) ____1:
```
Show answer
```
if len(arr) <=1:
```

Next lesson: Summary - Merge sort

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies