7 ms·
That analysis of spaghetti sort is incorrect as you scale N to a size larger than the hand. It will take time linear in the number of straws to move your hand a
by saurik 10y ago
That analysis of spaghetti sort is incorrect as you scale N to a size larger than the hand. It will take time linear in the number of straws to move your hand across the tips to find the largest one, and this will be true for any size hand as no matter how large the hand is, there is an upper limit to the number of straws it can hover over in parallel.
One of the big points of complexity analysis is that at small scales you might see certain behavior but what we are really interested in is asymptotic complexity: this is like saying selecting the lowest value from an unsorted array is faster than a tree iif the array has so few entries that it fits into the L1 cache (while the tree's randomly scattered memory means walking its left edge could take much longer; essentially making the array O(1) in memory accesses while the tree is O(log n)). A better analysis of spaghetti sort should find it to be O(n^2), if the algorithm really continues to function at all (and it isn't clear to me that it correctly scales).
(It is also worth nothing that if you want a limited purpose linear time sorting algorithm based on the same "let's change the notion of comparison", we even have working ones that function on real world computers: radix sort is insanely epic and with a little assistance from insertion sort fix up passes I have used it to sort Unicode strings in seemingly impossibly fast times.)