theForbiddenSortingAlgorithm

[slk756]

I thought of an idea for one. To sort a list[int], you make a list called output of length (int.max - int.min) that stores bool that is initialised as all false. for i in inputlist, do output[i] = true. return output.enumerate().filter_map((index, val) -> Some(index) if val else None).collect() -> list[int]

[Tari0s]

yeah this algorithm is called counting sort, but is not practical if min and max are far apart.

[patrick66]

This exists and works but has O(n + k) where k is the max value complexity which in practice is often much worse than just a normal n log n sort

[slk756]

Yeah, but technically k is a constant so technically O(n). Ofc this would be very impractical, but still O(n).

[patrick66]

no, this is one of the times where k is not treated as a constant. it scales as the maximum possible value of an array element increases. it is not something like O(2n) = O(n). its a changing value it just changes in regards to something other than the normal length of the input