sorting_recursive.py

#!python


def insertion_sort(items: list[int]) -> None:
    """Sort given items by taking first unsorted item, inserting it in sorted
    order in front of items, and repeating until all items are in order.
    Running time: O(n^2) worst case (reverse sorted), O(n) best case (already sorted)
    Memory usage: O(1), only creates a few variables, no matter how big the items list grows
    """
    # Repeat until all items are in sorted order
    # Take first unsorted item
    for current_position in range(1, len(items)):
        current_item = items[current_position]
        insert_position = current_position
        # Insert it in sorted order in front of items
        while insert_position > 0 and items[insert_position - 1] > current_item:
            items[insert_position] = items[insert_position - 1]
            insert_position -= 1
        items[insert_position] = current_item


def merge(items1: list[int], items2: list[int]) -> list[int]:
    """Merge given lists of items, each assumed to already be in sorted order,
    and return a new list containing all items in sorted order.
    Running time: O(n) where n is the total number of items in the two lists. Each item is processed one time under all conditions.
    Memory usage: O(n) where n is the total number of items in the two lists. A new list is created to store the merged result.
    """
    # Repeat until one list is empty
    # Find minimum item in both lists and append it to new list
    # Append remaining items in non-empty list to new list

    result = []
    left_index, right_index = 0, 0

    while left_index < len(items1) and right_index < len(items2):
        if items1[left_index] <= items2[right_index]:
            result.append(items1[left_index])
            left_index += 1
        else:
            result.append(items2[right_index])
            right_index += 1

    result.extend(items1[left_index:])
    result.extend(items2[right_index:])
    return result


def split_sort_merge(items: list[int]) -> list[int]:
    """Sort given items by splitting list into two approximately equal halves,
    sorting each with an iterative sorting algorithm, and merging results into
    a list in sorted order.
    Running time: O(n^2) on average because of the insertion sort and merge functions. Each call to insertion sort is O(n^2) and the merge function is O(n).
    Memory usage: O(n) because regardless of input order, we always create new lists."""
    # Split items list into approximately equal halves
    # Sort each half using any other sorting algorithm
    # Merge sorted halves into one list in sorted order
    mid = len(items) // 2
    left_half = items[:mid]
    right_half = items[mid:]

    insertion_sort(left_half)
    insertion_sort(right_half)

    return merge(left_half, right_half)


def merge_sort(items: list[int]) -> list[int]:
    """Sort given items by splitting list into two approximately equal halves,
    sorting each recursively, and merging results into a list in sorted order.
    Running time: O(n log n) because we split in half each time (O(log n)) and at each level, we do O(n) total work merging. Total: O(n) × O(log n) = O(n log n)
    Memory usage: O(n) because regardless of input order, we always create new lists."""
    # Check if list is so small it's already sorted (base case)
    if len(items) <= 1:
        return items

    # Split items list into approximately equal halves
    mid = len(items) // 2
    left_half = items[:mid]
    right_half = items[mid:]

    # Sort each half by recursively calling merge sort
    sorted_left_half = merge_sort(left_half)
    sorted_right_half = merge_sort(right_half)

    # Merge sorted halves into one list in sorted order
    merged_items = merge(sorted_left_half, sorted_right_half)

    for index in range(len(items)):
        items[index] = merged_items[index]
    return items


def partition(items: list[int], low: int, high: int) -> int:
    """Return index `p` after in-place partitioning given items in range
    `[low...high]` by choosing a pivot (middle-ish item) from
    that range, moving pivot into index `p`, items less than pivot into range
    `[low...p-1]`, and items greater than pivot into range `[p+1...high]`.
    Running time: O(n) because we loop through all items in the range once [low...high]
    Memory usage: O(1), we swap in place and don't create any new lists"""

    # Choose a pivot any way and document your method in docstring above
    pivot_index = (low + high) // 2
    pivot = items[pivot_index]

    # move pivot out of the way to not get swapped
    items[pivot_index], items[high] = items[high], items[pivot_index]

    # track where to place the next small element
    store_index = low

    # Loop through all items in range [low...high]
    for index in range(low, high):
        if items[index] < pivot:
            # Move items less than pivot into front of range [low...p-1]
            items[index], items[store_index] = items[store_index], items[index]
            store_index += 1

    # Move items greater than pivot into back of range [p+1...high]
    items[store_index], items[high] = items[high], items[store_index]

    return store_index


def quick_sort(items: list[int], low: int = None, high: int = None) -> None:
    """Sort given items in place by partitioning items in range `[low...high]`
    around a pivot item and recursively sorting each remaining sublist range.
    Best case running time: O(n log n) when we split the list in half each time.
    Worst case running time: O(n^2) when the list is already sorted or reverse sorted and list splits by one element each time.
    Memory usage: O(log n) on average when pivot splits close to evenly at each level
    """
    # Check if high and low range bounds have default values (not given)
    if low is None:
        low = 0
    if high is None:
        high = len(items) - 1

    # Check if list or range is so small it's already sorted (base case)
    if low >= high:
        return

    # Partition items in-place around a pivot and get index of pivot
    pivot_index = partition(items, low, high)

    # Sort each sublist range by recursively calling quick sort
    quick_sort(items, low, pivot_index - 1)
    quick_sort(items, pivot_index + 1, high)


if __name__ == "__main__":
    items1 = [0, 3]
    items2 = [1, 5, 6]
    # print(f"items1: {items1}")
    # print(f"items2: {items2}")
    print(f"merge result: {merge(items1, items2)}")
    print(f"expected: [0, 1, 3, 5, 6]")

    print("########################")

    # split_sort_merge
    items = [13, 1, 6, 4, 10]
    print(f"split sort merge result: {split_sort_merge(items)}")
    print(f"expected: [1, 4, 6, 10, 13]")

    print("########################")

    # merge_sort
    items = [13, 1, 6, 4, 10]
    print(f"merge sort result: {merge_sort(items)}")
    print(f"expected: [1, 4, 6, 10, 13]")

    print("########################")

    # partition
    items = [13, 1, 6, 4, 10]
    print(f"partition result: {partition(items, 0, len(items) - 1)}")
    print(f"expected: 2")

    print("########################")

    # quick_sort
    items = [13, 1, 6, 4, 10]
    quick_sort(items)
    print(f"quick sort result: {items}")
    print(f"expected: [1, 4, 6, 10, 13]")