3 ms·

The link to Sedgewick's 1978 paper no longer works, but an archive of it can be found here: http://web.archive.org/web/20190713031319/http://penguin.ewu.edu/csc

• kazinator 3y ago
  The paper says that more detailed discussion of partition methods is given in [15]. That looks like Sedwicks's Ph. D thesis which was on Quicksort? I found this: https://sedgewick.io/wp-content/themes/sedgewick/papers/1975Quicksort.pdf https://sedgewick.io/wp-content/themes/sedgewick/papers/1975... Basically a longer book on Quicksort with a lot more analysis. He doesn't discuss any partitioning methods that do not move two indices toward each other from opposite ends of the subarray. It's not even on the table.
  • metadat 3y ago
    Of course the logo on the paper title page is a sequence of 8 lines with each doubling on thickness. Though it'd be more visually and intuitively accurate if the lines started large and cut in half each step. :P
    • _the_inflator 3y ago
      Nice catch, yes!