PwnallthethingsFeb 16, 2023
Had to implement a sorting algorithm today for the first time in my entire career, so i guess finally learning about them decades ago paid off
Show threadPwnallthethingsFeb 16, 2023

Unfortunately since then, I've also learned about test-driven development, and forgotten everything I learned back then. So just went with

1. First implement a test routine "IsSorted(list)" to check the algorithm is right

Sort(list):
While(!IsSorted(list))
SwapRandomEntries(list);
return

Show threadPwnallthethingsFeb 16, 2023
Screw you computer science, computer go brrr.
Show threadSteve BellovinFeb 16, 2023
@Pwnallthethings The computational complexity of your solution is, umm, impressive…
Show threadPwnallthethingsFeb 16, 2023
@SteveBellovin but it works
Show threadSteve Bellovin
@Pwnallthethings And for reasonably small array sizes, it's not even too awful. Plus, you get your correctness test built-in. But for larger N—well, I wouldn't want to try that… (More seriously: as Kernighan has noted: first, get it right. Second, measure to find your real bottlenecks. Only then, optimize, and optimize in the right spots. In my formulation, there's no point to getting the wrong answer quickly.)
Feb 16, 2023 at 3:58amWeb
Show threadJohnMasheyFeb 16, 2023
@SteveBellovin @Pwnallthethings
And for *serious* sorting, Ordinal Technology's parallel nsort was already terrific in the 1990s on SGI multiprocessors (and others' as well):
2000 Paper by Ordinal's Chris Nyberg & Charles Koester & Microsoft's Jim Gray.
http://www.ordinal.com/NsortPara.pdf
Website: http://www.ordinal.com/
Show threadNicholas WeaverFeb 16, 2023
@SteveBellovin @Pwnallthethings
Relatedly, probably the most important concept we teach in the computer architecture class is Amdahl's law. "Only bother to optimize the bottlenecks", and programmer time matters too:
The runtime of your program is not just the runtime of your program, but the aggregate runtime of all invocations + the time it took you to write it in the first place.
Show threadPwnallthethingsFeb 16, 2023
@ncweaver @SteveBellovin 1000%. Which is why most libcs have weird aggressively hand-optimized memcpy routines, but qsort has stayed meh. Because qsort gets called almost never, and memcpy gets called so often in a normal run that even processor manufacturers come up with creative ways to do it faster.