Python Program to Implement Merge Sort

Merge Sort is a divide-and-conquer sorting algorithm that guarantees O(n log n) performance in every case — best, average, and worst — which makes it a dependable choice when consistency matters more than average-case speed. It's also the classic example used to teach recursion and the "merge" pattern that shows up again in problems like merging k sorted lists.

The idea: split the array in half repeatedly until each piece has one element (trivially sorted), then merge those pieces back together in sorted order.

Python Program to Implement Merge Sort

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left_half = merge_sort(arr[:mid])
    right_half = merge_sort(arr[mid:])

    return merge(left_half, right_half)


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

    # Append whatever is left over (one side is always fully consumed above)
    result.extend(left[i:])
    result.extend(right[j:])
    return result


numbers = [38, 27, 43, 3, 9, 82, 10]
print("Original:", numbers)
print("Sorted:", merge_sort(numbers))

Output:

Original: [38, 27, 43, 3, 9, 82, 10]
Sorted: [3, 9, 10, 27, 38, 43, 82]

The merge function is the key piece: since both left and right are already sorted (thanks to the recursive calls), merging them just means walking both lists once with two pointers and always taking the smaller front element — that single pass is what keeps the merge step at O(n). Combined with the O(log n) levels of splitting, the total work is O(n log n), with the trade-off being O(n) extra space for the temporary lists created during merging (unlike the in-place version of Quick Sort). This guaranteed worst-case behavior is why Merge Sort — or a hybrid like Python's own Timsort — is preferred for sorting linked lists and external (disk-based) sorting, where Quick Sort's worst case would be too risky.

---