This lesson's interactive features are locked, please to keep using them

Why Merge Sort?

Pros:

Fast: Merge sort is much faster than bubble sort. O(n*log(n)) instead of O(n^2).
Stable: Merge sort is a stable sort which means that values with duplicate keys in the original list will be in the same order in the sorted list.

Cons:

Memory usage: Most sorting algorithms can be performed using a single copy of the original array. Merge sort requires extra subarrays in memory.
Recursive: Merge sort requires many recursive function calls, and in many languages (like Python), this can incur a performance penalty.

Reference

def merge_sort(nums: list[int]) -> list[int]:
    if len(nums) < 2:
        return nums
    first = merge_sort(nums[: len(nums) // 2])
    second = merge_sort(nums[len(nums) // 2 :])
    return merge(first, second)


def merge(first: list[int], second: list[int]) -> list[int]:
    final = []
    i = 0
    j = 0
    while i < len(first) and j < len(second):
        if first[i] <= second[j]:
            final.append(first[i])
            i += 1
        else:
            final.append(second[j])
            j += 1
    while i < len(first):
        final.append(first[i])
        i += 1
    while j < len(second):
        final.append(second[j])
        j += 1
    return final