Interesting. We used to compare an n^2 sort with an n log n sort in Unit 5, where we do analysis of algorithms. That's one of the things we lost to meet teachers' complaints that there's too much in the curriculum, and that the sort algorithms are hard to teach, but I'd like to bring sorting back, at least as an optional project. I think U3 is a little early for it; among other reasons, we prefer to do exclusively functional programming on lists in the early units rather than getting into swapping items in place. So if we were going to put a partition sort (that's the generic term for quicksort-like things) in U3 I'd do it this way:
I picked the base case test I did because I'm imagining a linked list, for which LENGTH is O(n). This algorithm has a relatively high constant factor because it traverses the entire list three times, one for each KEEP. It also does redundant comparisons. Still, it's O(n log n), and it has the pedagogic virtue of being easy to understand and easy to get right (unlike the quicksort business of two pointers moving toward each other, which is prone to off-by-one errors).
But I much prefer mergesort, which is super elegant (imho, ymmv).
By the way, I was taught that it's not Quicksort unless it has all the bells and whistles, such as using median(first, last, middle) as the pivot (to guard against data coming in already sorted) and switching to insertion sort when n<6 or thereabouts, because for small n the asymptotic order of growth is swamped by the way smaller constant factor.
For some reason bubble sort gives me a headache; it took decades for me to convince myself that it actually works. I'm not suggesting that anyone else's teaching should suffer for my peculiarity about this. :~) But I like insertion sort, because it's nearly linear time when the data are largely in order, as happens, for example, when inserting today's new data into yesterday's sorted database.
PS One virtue of my partition sort is that it's stable, unlike Quicksort.