3 ms·
Tip: just count the number of zeroes Z, ones O, and twos T, and overwrite the array with, in order, Z zeroes, O ones, and T twos. You’ll iterate over the array
by Someone 6y ago
Tip: just count the number of zeroes Z, ones O, and twos T, and overwrite the array with, in order, Z zeroes, O ones, and T twos.
You’ll iterate over the array twice, but most of the time, you’ll beat anything more fancy because you’ll visit the items in a cache-friendly order.
If you say “that’s not sorting”, read your language spec. It likely has an “as if” clause that allows your (sufficiently smart; https://wiki.c2.com/?SufficientlySmartCompiler https://wiki.c2.com/?SufficientlySmartCompiler) compiler to make that transformation, if you give it enough info.