Implement Merge Sort and QuickselectStep 1 of 5

Merge two sorted lists

12345

Step 1: Merge two sorted lists

Divide-and-conquer sorting is built on one primitive: combining two lists that are already sorted into a single sorted list, in linear time.

Write merge(a, b) where a and b are each already sorted in ascending order. Return a NEW list containing every element of both, in sorted order.

Requirements:

  • Use two pointers, one into a and one into b.
  • Repeatedly take the smaller current element; when one list runs out, append the rest of the other.
  • Handle empty inputs: merging with an empty list returns a copy of the other.
  • Do not mutate a or b.

This linear-time merge is the engine behind merge sort in the next step.

Hints
Starter code
def merge(a, b):
    """Merge two already-sorted lists into a single sorted list."""
    # TODO: use two pointers i, j; append the smaller head each time, then the tail.
    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.

OverviewNext step