Last year, I was reading a fantastic paper on Quantum Mechanics for Kindergarden. It was not easy paper.Now, I wonder how to explain quicksort in the simplest words possible. How can I prove (or at least handwave) that the average complexity is $O(n \log n)$, and what the best and the worst cases are, to a kindergarden class? Or at least in primary school?
Quicksort explained to kids
algorithms;education;algorithm analysis;didactics;sorting
At its core, Quicksort is this:Take the first item.Move everything less than that first item to the left of it, everything greater to the right (assuming ascending order).Recurse on each side. I think every 4-year-old on the planet could do 1 and 2. The recursion might take a little bit more explanation, but shouldn't be that hard for them.Repeat on the left side, ignoring the right for now (but remember where the middle was)Keep repeating with the left sides until you get to nothing. Now go back to the last right side you ignored, and repeat the process there.Once you run out of right and left sides, you're done.As for the complexity, worst-case should be fairly easy. Just consider an already-sorted array:1 2 3 4  2 3 4    3 4      4Fairly easy to see (and prove) that it's $\frac{1}{2}n^2$.I'm not familiar with the average-case proof, so I can't really make a suggestion for that. You could say that in an unsorted array of length $l$ the probability of picking the smallest or largest item is $\frac{2}{n}$, so...?