a pure python implementation of quick sort algorithminplace with lomuto partition scheme https en wikipedia orgwikiquicksortlomutopartitionscheme param sorting sort list param left left endpoint of sorting param right right endpoint of sorting return none examples nums1 0 5 3 1 2 quicksortlomutopartitionnums1 0 4 nums1 0 1 2 3 5 nums2 quicksortlomutopartitionnums2 0 0 nums2 nums3 2 5 0 4 quicksortlomutopartitionnums3 0 3 nums3 4 2 0 5 example lomutopartition1 5 7 6 0 3 2 threeway radix quicksort https en wikipedia orgwikiquicksortthreewayradixquicksort first divide the list into three parts then recursively sort the less than and greater than partitions threewayradixquicksort threewayradixquicksort1 1 threewayradixquicksort5 2 1 2 0 1 5 2 2 0 1 1 threewayradixquicksort1 2 5 1 2 0 0 5 2 1 1 0 0 1 1 2 2 2 5 5 a pure python implementation of quick sort algorithm in place with lomuto partition scheme https en wikipedia org wiki quicksort lomuto_partition_scheme param sorting sort list param left left endpoint of sorting param right right endpoint of sorting return none examples nums1 0 5 3 1 2 quick_sort_lomuto_partition nums1 0 4 nums1 0 1 2 3 5 nums2 quick_sort_lomuto_partition nums2 0 0 nums2 nums3 2 5 0 4 quick_sort_lomuto_partition nums3 0 3 nums3 4 2 0 5 example lomuto_partition 1 5 7 6 0 3 2 three way radix quicksort https en wikipedia org wiki quicksort three way_radix_quicksort first divide the list into three parts then recursively sort the less than and greater than partitions three_way_radix_quicksort three_way_radix_quicksort 1 1 three_way_radix_quicksort 5 2 1 2 0 1 5 2 2 0 1 1 three_way_radix_quicksort 1 2 5 1 2 0 0 5 2 1 1 0 0 1 1 2 2 2 5 5
def quick_sort_3partition(sorting: list, left: int, right: int) -> None:
    if right <= left:
        return
    a = i = left
    b = right
    pivot = sorting[left]
    while i <= b:
        if sorting[i] < pivot:
            sorting[a], sorting[i] = sorting[i], sorting[a]
            a += 1
            i += 1
        elif sorting[i] > pivot:
            sorting[b], sorting[i] = sorting[i], sorting[b]
            b -= 1
        else:
            i += 1
    quick_sort_3partition(sorting, left, a - 1)
    quick_sort_3partition(sorting, b + 1, right)


def quick_sort_lomuto_partition(sorting: list, left: int, right: int) -> None:
    
    if left < right:
        pivot_index = lomuto_partition(sorting, left, right)
        quick_sort_lomuto_partition(sorting, left, pivot_index - 1)
        quick_sort_lomuto_partition(sorting, pivot_index + 1, right)


def lomuto_partition(sorting: list, left: int, right: int) -> int:
    
    pivot = sorting[right]
    store_index = left
    for i in range(left, right):
        if sorting[i] < pivot:
            sorting[store_index], sorting[i] = sorting[i], sorting[store_index]
            store_index += 1
    sorting[right], sorting[store_index] = sorting[store_index], sorting[right]
    return store_index


def three_way_radix_quicksort(sorting: list) -> list:
    
    if len(sorting) <= 1:
        return sorting
    return (
        three_way_radix_quicksort([i for i in sorting if i < sorting[0]])
        + [i for i in sorting if i == sorting[0]]
        + three_way_radix_quicksort([i for i in sorting if i > sorting[0]])
    )


if __name__ == "__main__":
    import doctest

    doctest.testmod(verbose=True)

    user_input = input("Enter numbers separated by a comma:\n").strip()
    unsorted = [int(item) for item in user_input.split(",")]
    quick_sort_3partition(unsorted, 0, len(unsorted) - 1)
    print(unsorted)