Sorting in-place with minimum data movement
Venkatesh Raman · 1992
Sorting is a fundamental problem in Computer Science. The two main operations in sorting are comparisons and movements. Traditional algorithms and lower bounds for sorting centered on minimizing the number of comparisons needed. However, when each element of the list to be sorted is too large to move frequently, movement also becomes a significant operation. This thesis re-examines sorting with a special emphasis on the operation data movement. We focus on the scenario when the amount of extra storage available is severely restricted relative to the amount of to be sorted. Our interest is on in-place algorithms, those that use a constant number of extra storage cells. We present several new in-place sorting algorithms satisfying constraints on the number of movements. We first present an exact lower bound for the number of movements required to sort any given list, in terms of the number of cycles in the permutation required to sort the list. We also design algorithms that achieve this optimum bound (on a given list) using little or no extra storage. En route to this problem we come across a more natural problem: selecting an item of arbitrary rank, from a list of elements residing in a read-only memory. We develop time and space efficient algorithms for this selection problem. All known O(n lg n) sorting algorithms perform $\Theta$(n lg n) movements or use $\Theta$(n) extra words of storage. We develop a computational model that captures comparisons, movements and extra storage in sorting. Using that we characterize the approach of several well-known algorithms, based on the comparisons made before a move. Following an alternate approach based on random sampling, we design an in-place sorting algorithm that performs O(n) movements in the worst case, and O(n lg n) comparisons on the average. Several variations of the algorithm are also presented. We also devise the first in-place sorting algorithm that is stable (i.e. maintain the relative order of equal valued items) and performs O(n) movements. When the list consists of a constant number of distinct keys, we develop fast stable in-place algorithms resulting in a stable in-place version of Quicksort. Finally, we present the first worst-case optimal in-place sorting algorithm that is adaptive to the presence of equal valued keys. We apply that to obtain an optimal in-place algorithm to lexicographically sort a list of vectors.