Stable Sorting in Asymptotically Optimal Time and Extra Space

Abstract

A stable sorting algonthm is one which does not permute the relative order of records which have equal keys. In The Art of Computer Programming, Vol 3, Exercise 5 5-3, Knuth poses the problem of finding a stable sorting algorithm which requires less than O(N ~2) time to sort N records, for arbitrary N, and which also requires no more than O(log N) bits of extra space (space in excess of that required to hold the N records)