sorting.py

def partition(arr, sort_key, low, high):
    """
    Partitions arr[low..high] around pivot arr[high] based on sort_key.

    Args:
        arr: List of dictionaries to partition (modified in-place).
        sort_key: Dictionary key to use for value comparison.
        low: Starting index of the sub-array.
        high: Ending index (and pivot index) of the sub-array.

    Returns:
        The final index of the pivot element after partitioning.
    """
    pivot = arr[high][sort_key]
    
    i = low - 1
    for j in range(low, high):
        if arr[j][sort_key] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i] 
    
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i + 1

def quicksort(arr, sort_key, low, high):
    """
    Sorts a list of dictionaries in-place using quicksort.

    Recursively sorts the sub-list `arr[low..high]` based on `sort_key`.

    Args:
        arr: The list of dictionaries to sort (modified in-place).
        sort_key: Dictionary key to use for value comparison.
        low: Starting index for sorting.
        high: Ending index for sorting.

    Returns:
        The list `arr`, sorted in-place between `low` and `high`.
    """
    if low < high:
        pivot_index = partition(arr, sort_key, low, high)
        quicksort(arr, sort_key, low, pivot_index - 1)
        quicksort(arr, sort_key, pivot_index + 1, high)
    return arr

def quicksort_dict(results, sort_key):
    """
    Sorts the lists within a dictionary using quicksort based on sort_key.

    Args:
        results: Dictionary where values are lists of dictionaries to be sorted.
        sort_key: Dictionary key within the inner lists' dicts for sorting.

    Returns:
        A new dictionary with the same keys, but with sorted list values.
        (Note: The lists themselves are sorted in-place).
    """
    sorted_dict = {}
    for key, routes in results.items():
        sorted_dict[key] = quicksort(routes, sort_key, low=0, high=len(routes)-1)
    return sorted_dict