сортировка почти отсортированных данных

From

Max Alekseyev (2:5015/60)

To

All

Date

2002-07-15T20:29:32Z

Area

RU.ALGORITHMS

████ OS/2        Hi, All !

Предположим, что массив данных размерности n является почти отсортированным (чтобы формализовать это понятие, скажем, достаточно не более log(n) элементарных операций для получения из него отсортированного массива). Какие есть алгоритмы для быстрой сортировки таких массивов? Хотелось бы линейного времени, а лучше саб-линейного.

Regards,      °°
        Max    ~

--- FleetStreet 1.27.3.8
 * Origin:  (2:5015/60)