Re:Lambdasort: Quicksort written in Python only using lambdas
by qsort on Tuesday January 02, 2024 @08:07PM
(#38849424)
The entire point of quicksort is that it doesn't allocate and its inner loop is very tight (especially if you don't use Lomuto partitioning -- they teach Lomuto partitioning in school because the proof of correctness is easier).
Writing it in the naive functional-like style is fun and instructive, but it doesn't quite strike at the heart of what quicksort is about.
It's an example of an instance where the functional setting makes it harder to reason about the program.
It misses the point though that it takes a handful of lines to write Quicksort in a functional programming language as opposed to 50 or so lines in BASIC or FORTRAN 77. Of course most of us these days aren’t old enough to remember writing a Quicksort in languages like that and might not appreciate the difference but you might as well code it in assembly language as in an old language that doesn’t support recursion.