# Interval Sorting

Conrado Martinez (UPC, Barcelone)In the interval sort problem, we are given an array *A* of *n* items and *p*
ranges of ranks *I* 1=[ *l* 1, *u* 1], …, *I* *p* =[ *l* *p* , *u* *p* ].
The goal is to rearrange the array so that *A* [ *l t*.. *u t*] contains the
*l t*-th, …, *u t*-th smallest elements of *A* in nondecreasing order, for
all *t* , 1 ≤ *t* ≤ *p* , and *A* [ *u t*+1.. *l* *t* +1-1] contains the ( *u
t*+1)-th, …, ( *l* *t* +1-1)-th smallest elements of *A* , for all *t, 0 ≤ t
≤* p. That is, the array is sorted by blocks, with sorted and unsorted blocks
alternating. One of the most interesting aspects of this research is the
unification of several important and related problems (sorting, selection,
multiple selection, partial sorting) under a single framework. Results on
interval sorting generalize the results for any of these particular—and
fundamental—problems.

We propose a divide-and-conquer algorithm, owing to quicksort and quickselect,
named chunksort, to solve the problem. We give an exact expression for the
average number of comparisons made by the basic variant of chunksort. Then we
consider what is the expected optimal number of comparisons needed to solve an
interval sort instance and we design a variant of chunksort that achieves near
optimal expected performance, up to *n* + *o* ( *n* ) comparisons. In fact, we
conjecture that the algorithm that we propose has actually optimal expected
performance up to *o* ( *n* ) terms and provide some evidence for this
conjecture. To describe our near-optimal solution to interval sorting, I will
also discuss some of my previous work on optimal quicksort and on optimal
quickselect.

This is joint work with Rosa M. Jimenez.