Implement Merge Sort and QuickselectStep 2 of 5

Merge sort

12345

Step 2: Merge sort

Now turn merge into a full sort. Merge sort splits the list in half, sorts each half recursively, then merges the two sorted halves back together.

Write merge_sort(arr) that returns a NEW sorted list. Do not mutate arr.

Requirements:

  • Base case: a list of length 0 or 1 is already sorted. Return a copy.
  • Otherwise split at the midpoint, recurse on each half, and combine the results with your merge function from Step 1.

Merge sort runs in O(n log n) time and is stable, which we will exploit in Step 5.

Hints
Starter code
def merge(a, b):
    result = []
    i = j = 0
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            result.append(a[i])
            i += 1
        else:
            result.append(b[j])
            j += 1
    result.extend(a[i:])
    result.extend(b[j:])
    return result


def merge_sort(arr):
    """Return a new sorted list using recursive divide-and-merge."""
    # TODO: base case len<=1; split at mid; recurse; combine with merge().
    pass
Write it on a laptop

The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.

PreviousNext step