Dutch National Flag Problem Running In O(n)

I am a 10th-grade student in CompSci 1. In our textbook, Practical Programming 3rd Edition, An Introduction to Computer Science Using Python 3.6, it mentions the Dutch National Fl

Solution 1:

What you show is a counting sort. Other non-comparison options would be bucket or radix sort that also have O(n) time complexity.

It's also possible to solve this problem with a comparison based 3-way partition function that uses compares and swaps with time complexity O(n).

https://en.wikipedia.org/wiki/Dutch_national_flag_problem#Pseudocode

Normally comparison based sorts take O(n log(n)) time, but the Dutch national flag problem doesn't require this.

The 3 way partition function can be expanded to handle a larger number of colors. The first pass separates the array into 3 sub-arrays, small, middle, large, then repeats the process on each sub-array to split it into 3 sub-sub arrays and so on. 9 colors could be done in 2 passes, 1st pass separates into small, middle, large, then 2nd pass separates each sub-array into 3 parts, which is also O(n) time complexity. For n elements and k colors, the time complexity is O(n⌈log3(k)⌉), but since k is a constant, the time complexity is O(n).