Implementing Recursive Merge Sort

The function’s contract accepts a list of mutually comparable values and returns a new sorted list. It leaves the caller’s original list unchanged. An input of length zero or one is already sorted; return a shallow copy directly. Otherwise split at len(values)//2, recursively sort the left and right slices, and merge those sorted results.

The base case must handle an empty list as well as a singleton. Each recursive slice is shorter than the original nontrivial input, giving progress towards termination. A recursive function call does not automatically make an arbitrary operation correct: the merge step relies on both child results already being sorted under the same comparison rule.

Use two indices, initially zero, into the sorted child lists. Compare their current values and append the smaller one, advancing only that child’s index. The output is a sorted prefix containing exactly the child items already consumed. When one child is exhausted, append the remaining suffix of the other, because that suffix is already sorted.

Choosing the left item on an equal comparison preserves the original relative order of equal-key items across the split. This is the stability property, assuming comparisons use the intended key consistently. Choosing the right equal item can still sort the numerical values but changes that stability guarantee. Keep correctness properties separate: sorted order alone does not prove that every input value survived.

For [7,2,5,2], the left child sorts to [2,7] and the right to [2,5]. The merge takes the left 2, the right 2, then 5 and 7. A correct result contains both copies of 2. Compare its multiset with the original and confirm the source list still has its original order. Add empty, singleton, all-equal, already sorted and reverse-order tests.

At each approximately balanced recursion level, merging costs a total proportional to n, with O(log n) levels, so this implementation takes O(n log n) comparison work in the usual model. Its arrays/slices and merge results require additional memory; it is not an in-place constant-space sort. For production Python, built-in sorting is usually preferable, but the examination skill here is implementing and explaining the algorithm.

def merge_sort(values):
    if len(values) <= 1:
        return values[:]
    middle = len(values) // 2
    left = merge_sort(values[:middle])
    right = merge_sort(values[middle:])
    merged = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i])
            i += 1
        else:
            merged.append(right[j])
            j += 1
    merged.extend(left[i:])
    merged.extend(right[j:])
    return merged

original = [7, 2, 5, 2]
print(merge_sort(original))
print(original)

Attempt the task before opening its worked response. Record each change of state, explain the rule used, and check the result against the original requirements. Code examples labelled Python 3 use that language’s conventions; pseudocode states its own assumptions.