On adaptive sorting in sequential and parallel models

Sammanfattning:

Sorting is probably the most well-studied problem in computer science. In many applications the elements to be sorted are not randomly distributed, but are already nearly ordered. Most existing algorithms do not take advantage of this fact. In this thesis, the problem of utilizing existing order among the input sequence, yielding adaptive sorting algorithms, is explored. Different measures for measuring existing order are proposed; all motivated by geometric interpretations of the input. Furthermore, several adaptive, sequential and parallel, sorting algorithms are provided.

The thesis consists of three papers. The first paper studies the local insertion sort algorithm of Mannila, and proposes some significant improvements. The second provides an adaptive variant of heapsort, which is space efficient and uses simple data structures. In the third paper, a cost-optimal adaptive parallel sorting algorithm is presented. The model of computation is the EREW PRAM.