As an exercise, when could spaghetti sort beat computers? As others have mentioned, your hand can only hold so much pasta (about 10^2). For n=10^2, a computer

As an exercise, when could spaghetti sort beat computers? As others have mentioned, your hand can only hold so much pasta (about 10^2). For n=10^2, a computer will easily win. So I'll need to abuse logic a bit... Let's assume - The hand is large enough to hold all the pasta. - The linear time operations take about 1 second total (breaking, removing, transcribing). Benchmarks[1] for sorting show TencentSort (which looks like it's based on a O(nlog(n)) merge sort[2]?) can sort 100TB in 100 seconds, for 100 byte records. So about 10^12 records/minute. c*(n*log(n))=time n=10^12 time=1min c~=1/10^12 minute (assume log base 2) Solving: (1/10^12)*n*log(n)=n (1/10^12)*log(n)=1 log(n)=10^12 log(n)=1,000,000,000,000 n=2^1,000,000,000,000 How big is that? A piece of spaghetti is about 1 gram. 2^1,000,000,000,000 grams is significantly larger than the mass of the observable universe. (10^56 grams, or 2^186 grams). How long is that? 2^56 seconds is the age of the universe. Intuitively, this sort of makes sense. For extremely large values of n, log(n) is dwarfed by n so much that it looks like just n. A computer performing a single step of the sort operation is several orders of magnitude faster than any of the human operations. It takes insanely long, and an insanely large n for spaghetti sort to catch up. [1] https://sortbenchmark.org/ https://sortbenchmark.org/ [2] http://sortbenchmark.org/TencentSort2016.pdf http://sortbenchmark.org/TencentSort2016.pdf