Dutch National Flag

Problem

Sort a list containing only the values 0, 1 and 2 in ascending order and return the sorted list.

Use the three-pointer Dutch national flag partition: a low pointer for the boundary of zeros, a mid pointer scanning forward and a high pointer for the boundary of twos. The array is sorted in a single pass without counting.

Hint

After swapping a two to the back, do not advance mid because the new element is unexamined.

Test cases

case 1

in: [[2,0,2,1,1,0]]

expected: [0,0,1,1,2,2]

case 2

in: [[]]

expected: []

case 3

in: [[0]]

expected: [0]

case 4

in: [[1,0,2,0,1,2]]

expected: [0,0,1,1,2,2]

case 5

in: [[2,2,1,1,0,0]]

expected: [0,0,1,1,2,2]

Starter codePython

def sort_colors(arr):
    # Your code here
    pass

5 test cases · run your code against them in the editor