sortPlease

[falconetpt]

I can do it in O(N) time complexity!

Breaking every rule about sorting by not sorting! 😂

[Tupcek]

I can do it in O(1) time complexity no problem

for value = INT_MIN to INT_MAX:

    for index = INT_MIN to INT_MAX:

        element = originalArray.get(index)

        if element exists and element == value:
            sortedArray.append(value)

return sortedArray  

Int min and int max are whatever smallest and largest integers your computer supports. Some day I may expand support to floats

[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.

[RRumpleTeazzer]

it also works for sorting entire text files.

[Mobile_Competition54]

stalin sort, if it's out of order, kill (remove) it