array of 0's and 1's sort the array in O(n) code example

Example: Sort an array of 0’s, 1’s and 2’s

# Utility function to swap elements `A[i]` and `A[j]` in the list
def swap(A, i, j):
 
    temp = A[i]
    A[i] = A[j]
    A[j] = temp
 
 
# Linear time partition routine to sort a list containing 0, 1, and 2.
# It is similar to 3–way partitioning for the Dutch national flag problem.
def threeWayPartition(A, end):
 
    start = mid = 0
    pivot = 1
 
    while mid <= end:
        if A[mid] < pivot:    # current element is 0
            swap(A, start, mid)
            start = start + 1
            mid = mid + 1
        elif A[mid] > pivot: # current element is 2
            swap(A, mid, end)
            end = end - 1
        else:                # current element is 1
            mid = mid + 1