Implement Merge Sort and QuickselectStep 3 of 5

Partition and quicksort

12345

Step 3: Partition and quicksort

Quicksort takes a different divide-and-conquer route: pick a pivot, rearrange the list so smaller elements sit left of the pivot and larger ones sit right, then sort each side.

First write partition(arr, lo, hi) using the Lomuto scheme with a FIXED pivot of arr[hi] (the last element). Rearrange arr[lo..hi] IN PLACE and return the final index of the pivot.

Then write quick_sort(arr) that returns a NEW sorted list (copy first, then partition recursively. Do not mutate the caller's list).

Using a fixed pivot keeps the behavior fully deterministic.

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):
    if len(arr) <= 1:
        return list(arr)
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)


def partition(arr, lo, hi):
    """Lomuto partition around the fixed pivot arr[hi]; return pivot index."""
    # TODO: keep boundary i; swap elements <= pivot forward; place pivot at i.
    pass


def quick_sort(arr):
    """Return a new sorted list using partition (do not mutate input)."""
    # TODO: copy arr; recursively partition sublists around the pivot index.
    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