I think the big-O coding question may require this knowledge, because

….real world sorting problems can often use **key-based** sorting, rather than comparison-based sorting.

Therefore, if your overall solution requires sorting, don’t assume it would become O(J*K+M^2+P*N logN) based on your O(N logN) sorting assumption. Here are some achievable linear-time sorts:

sort | O() | data type | ref | notes | ||

counting | O(N) | chars | ||||

radix | O(N) | 64-bit ints | O(Nw) -> O(N) | |||

radix | O(N) | variable-size strings | [1][2] | fastest | ||

burst | O(N) | variable-size strings | 2nd fastest. key-based, trie-based | |||

radix | O(N) | floats | [3] | IEEE format | ||

radix | O(N) | date/time | converting to fixed-length string or fixed-size integers | |||

bucket? | O(N) | random ints in python/perl |
unbounded. No limit on #digits | |||

Note if data is nearly sorted, then insertion-sort will outperform everyone else.

[1] https://www.cs.princeton.edu/~rs/AlgsDS07/18RadixSort.pdf

[2] https://link.springer.com/chapter/10.1007%2F978-3-540-89097-3_3 paper presented a MSD radix sort for large collections of strings, faster than any other string sorting algorithm.

[3] http://www.boost.org/doc/libs/1_59_0/libs/sort/doc/html/sort/sort_hpp/float_sort.html