Merge Sort

Understand the idea

During merging, choose the smaller front value and advance only that side. Using <= selects the left equal value first, giving stability in this version. Time is O(n log n) for ordinary comparisons, with extra memory for copied halves and results. A linked-list merge implementation would have different storage tradeoffs.

Where to try it

Open this example with Try in playground. The code loads as editable text and does not run until you select Run. The first run downloads Python. Each run starts fresh; temporary files created by a script are not files on your PC.

A worked example

def merge_sort(values):
    if len(values) < 2:
        return list(values)
    middle = len(values) // 2
    left = merge_sort(values[:middle])
    right = merge_sort(values[middle:])
    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
    return result + left[i:] + right[j:]

print(merge_sort([8, 3, 5, 3]))

Read the result

The result is [3, 3, 5, 8]. Any unconsumed tail is appended after one half empties.

Try one change

Compare the result with sorted for empty, repeated, sorted, and reverse-sorted small inputs.