Скорость сортировки слиянием

← →
TUser © (2004-04-06 10:24) [0]

Помогите, pzl, оценить скорость работы такого алгоритма сортировки. На входе - двумерный массив, который представляет собой половинку квадратной матрицы. Т.е. у него есть элементы (0,0), (1,0), (1,1), (2,0), (2,1), (2,2) и т.д. На выходе должен быть одномерный массив [0..k*(k+1)/2-1] (к - число "строк"), составленный из элементов исходного массива. Исходный массив должен остаться без изменений. Кроме того, там еще некоторые штуки на выходе получаются, но это не важно.
Я для сортировки применил такую вот модификацию сортировки слиянием. При обычной сортировке слиянием массив разбивается на отрезки одинаковой длины. Но здесь уже массив исходно разделен на отрезки длины 1, 2, ..., k. Поэтому сначала я отсортировал все эти строки. Потом принялся объединять. Для объединения всего этого дела хранится массив, в котором записываются границы уже просмотренных участков для каждой строчки. На каждом этапе объединения перебираем все строчки, находим минимум и добавляем его в массив-результат.
Вобще-то я от такого алгоритма отказался, т.к. он не очень оптимален с точки зрения использования памяти. Проще загонять элементы в одномерный массив и там уже сортировать. Но хотелось бы получить оценку скорости такого алгоритма.
Сортировка строк занимает 1+2^2+3^2+4^2+...+k^2~k^3~n^(1.5). А вот как оценить скорость объединения строк в единый массив?

PS. Хотел в Потрепаться - но туда с 3х попыток не добавилось. Поэтому сюда.

← →
TUser © (2004-04-06 18:26) [1]

А сверху быть лучше ...

← →
Serginio666 (2004-04-06 18:55) [2]

Вообще то сортировка слиянием процентов 10 уступает QuickSort
http://www.rsdn.ru/forum/Message.aspx?mid=577195&only=1

По сравнению с QuickSort меньше сранений но больше переносов.
Но на хорошей памяти и шине это не проблема.

← →
Serginio666 (2004-04-06 20:04) [3]

Да в отличие от QuickSort сортировка слиянием стабильна, и если памяти много тоее использование даже предпочтительней. Правда не тестил структуры, там ситуация возможна другая.

Скорость сортировки слиянием Найти похожие ветки