a pure implementation of dutch national flag dnf sort algorithm in python dutch national flag algorithm is an algorithm originally designed by edsger dijkstra it is the most optimal sort for 3 unique values eg 0 1 2 in a sequence dnf can sort a sequence of n size with 0 ai 2 at guaranteed on complexity in a single pass the flag of the netherlands consists of three colors white red and blue the task is to randomly arrange balls of white red and blue in such a way that balls of the same color are placed together dnf sorts a sequence of 0 1 and 2 s in linear time that does not consume any extra space this algorithm can be implemented only on a sequence that contains three unique elements 1 time complexity is on 2 space complexity is o1 more info on https en wikipedia orgwikidutchnationalflagproblem for doctests run following command python3 m doctest v dutchnationalflagsort py for manual testing run python dnfsort py python program to sort a sequence containing only 0 1 and 2 in a single pass a pure python implementation of dutch national flag sort algorithm param data 3 unique integer values e g 0 1 2 in an sequence return the same collection in ascending order dutchnationalflagsort dutchnationalflagsort0 0 dutchnationalflagsort2 1 0 0 1 2 0 0 1 1 2 2 dutchnationalflagsort0 1 1 0 1 2 1 2 0 0 0 1 0 0 0 0 0 1 1 1 1 1 2 2 dutchnationalflagsortabacab traceback most recent call last valueerror the elements inside the sequence must contains only 0 1 2 values dutchnationalflagsortabacab traceback most recent call last valueerror the elements inside the sequence must contains only 0 1 2 values dutchnationalflagsort3 2 3 1 3 0 3 traceback most recent call last valueerror the elements inside the sequence must contains only 0 1 2 values dutchnationalflagsort1 2 1 1 1 0 1 traceback most recent call last valueerror the elements inside the sequence must contains only 0 1 2 values dutchnationalflagsort1 1 2 1 1 1 1 1 0 1 1 traceback most recent call last valueerror the elements inside the sequence must contains only 0 1 2 values python program to sort a sequence containing only 0 1 and 2 in a single pass the first color of the flag the second color of the flag the third color of the flag a pure python implementation of dutch national flag sort algorithm param data 3 unique integer values e g 0 1 2 in an sequence return the same collection in ascending order dutch_national_flag_sort dutch_national_flag_sort 0 0 dutch_national_flag_sort 2 1 0 0 1 2 0 0 1 1 2 2 dutch_national_flag_sort 0 1 1 0 1 2 1 2 0 0 0 1 0 0 0 0 0 1 1 1 1 1 2 2 dutch_national_flag_sort abacab traceback most recent call last valueerror the elements inside the sequence must contains only 0 1 2 values dutch_national_flag_sort abacab traceback most recent call last valueerror the elements inside the sequence must contains only 0 1 2 values dutch_national_flag_sort 3 2 3 1 3 0 3 traceback most recent call last valueerror the elements inside the sequence must contains only 0 1 2 values dutch_national_flag_sort 1 2 1 1 1 0 1 traceback most recent call last valueerror the elements inside the sequence must contains only 0 1 2 values dutch_national_flag_sort 1 1 2 1 1 1 1 1 0 1 1 traceback most recent call last valueerror the elements inside the sequence must contains only 0 1 2 values
red = 0  
white = 1  
blue = 2  
colors = (red, white, blue)


def dutch_national_flag_sort(sequence: list) -> list:
    
    if not sequence:
        return []
    if len(sequence) == 1:
        return list(sequence)
    low = 0
    high = len(sequence) - 1
    mid = 0
    while mid <= high:
        if sequence[mid] == colors[0]:
            sequence[low], sequence[mid] = sequence[mid], sequence[low]
            low += 1
            mid += 1
        elif sequence[mid] == colors[1]:
            mid += 1
        elif sequence[mid] == colors[2]:
            sequence[mid], sequence[high] = sequence[high], sequence[mid]
            high -= 1
        else:
            msg = f"The elements inside the sequence must contains only {colors} values"
            raise ValueError(msg)
    return sequence


if __name__ == "__main__":
    import doctest

    doctest.testmod()

    user_input = input("Enter numbers separated by commas:\n").strip()
    unsorted = [int(item.strip()) for item in user_input.split(",")]
    print(f"{dutch_national_flag_sort(unsorted)}")