Quicksort in Constant Space

Authors

Anne Kaldewaij, Washington University in St Louis
Jan Tijmen Udding, Washington University in St Louis

Document Type

Technical Report

Publication Date

1991-01-01

Filename

WUCS-91-20.pdf

Technical Report Number

WUCS-91-20

Abstract

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.

Comments

Permanent URL: http://dx.doi.org/10.7936/K78G8J23

Recommended Citation

Kaldewaij, Anne and Udding, Jan Tijmen, "Quicksort in Constant Space" Report Number: WUCS-91-20 (1991). All Computer Science and Engineering Research.
https://openscholarship.wustl.edu/cse_research/638