2 ms·
> I think my first iteration used bubble sort. That was still faster than a sort | head script, by a lot. Haha! Gotta get Barack Obama to give you some algori
by kragen 5y ago
> I think my first iteration used bubble sort. That was still faster than a sort | head script, by a lot.
Haha! Gotta get Barack Obama to give you some algorithms lessons.
Thinking about it further, the initial heapify phase of heapsort is linear-time, and it's the later heap-popping phase that takes most of the runtime; if the command-line `sort` used heapsort for in-memory data, maybe `sort | head` would have been competitive or even faster? At least for n>32 or so? The usual algorithm for `sort` is mergesort, because that makes it perform acceptably for things that don't fit in RAM, but mergesort has to do most of its work before it can start producing output.