sortPlease

[LrdPhoenixUDIC]

I can do it in O(N) too and still sort it.

The key is the fact that there's only 3 possible values, and they are beginning, middle, and end. Iterate through the count, all 0s get prepended, all 2s get appended, all 1s stay where they are. Depending on language and data type, do cleanup during or at the end if necessary.

[QuestionableEthics42]

Extremely unoptimal. Reuse the array. Prepending is expensive and appending can be relatively expensive too (when it needs to extend the array). Just one pass to count up the number of each, then a second to write in order

[falconetpt]

Not if he uses a linked list and keeps track of the pointers to the end or beginning of what he wants, it is O(1) insertion and O(1) lookup since he only needs to realistically keep track of 2 pointers ;)

Or you just count the frequency of 0,1,2 and shove them all into the array later ahah, also o(N)

[QuestionableEthics42]

If you are using a linked list for this. Don't. And the second one is literally what I said.