Technical Report Number
An in situ sorting algorithm, based on Quicksort, is presented with its proof of correctness. The proof illustrates a concise and elegant way to represent a sequence that has been partially sorted by Quicksort. A list representation turns out to be well suited to this purpose, and the discussion is entirely in terms of lists.
Kaldewaij, Anne and Udding, Jan Tijmen, "Quicksort in Constant Space" Report Number: WUCS-91-20 (1991). All Computer Science and Engineering Research.