quote:Original post by DrPizza
Place the pasta on a table, thin ends down. Then pick the tallest piece of pasta (constant time). Continue picking the tallest piece of pasta until you have them all in order (linear time).
Hmmm. It is indeed similar to the selection sort.
I don''t think it''s a fair assumption that choosing the longest piece of pasta is O(1); what if you have a 100-km long line of strands?
quote:Original post by benjamin bunny
I didn''t know a radix sort could be that flexible. Still, it eats a huge amount of memory.
Compared to other sorting algorithms, it does use a lot of memory, but I don''t think it''s "huge".
For sorting arrays, the implementation I use allocates an equally-sized array, plus 256 ints.
For linked lists, I think it requires 512 pointers and nothing more.
quote:Original post by benjamin bunny
My method (superSort) combines that with a bubble sort to improve the speed.
Look through these for the "fast quicksort". Same idea, but it uses the insertion sort instead of the bubblesort.