[слияние]Внешняя сортировка

В Википедии написано про сортировку слияением:

Sorting in-place is possible (e.g., using lists rather than arrays) but is very complicated, and will offer little performance gains in practice, even if the algorithm runs in O(n log n) time. In these cases, algorithms like heapsort usually offer comparable speed, and are far less complex. Additionally, unlike the standard merge sort, in-place merge sort is not a stable sort. In the case of linked lists the algorithm does not use more space than that the already used by the list representation, but the O(log(k)) used for the recursion trace.

Ну и собственно в сравнении разных методов сортировки написано:

Тип: In-place merge sort
Худший случай: n*log(n)
В среднем: n*log(n)
Память: 1
Стабильная: Depends
Метод: Merging

Ну и ссылки даны, можешь глянуть.

Вместо тупого сидения в интернете надо осилить Д. Кнута и Р. Седжвика.

было интересно мнение «ослившего» ЛОРа, и вопрос был именно про слияние в контексте внешней сортировки, потому как она обладает некоторыми специфическими особенностями(про алгоритм Пратта я знаю, но он выглядит не очень для внешней сортировки, нашел получше)

Спасибо, использую этот алгоритм слияния: время O(n), память O(1)

http://docs.google.com/viewer?a=v&q=cache:XeE62nr2mbkJ:citeseerx.ist.psu.edu/...

вот тебе пример для inplace Субж.: Mergesort For Linked Lists

он не требует дополнительной памяти, но он не inplace

and also preparing an empty list L which we will add elements to the end of as we finish dealing with them.

А дополнитеьлная память не требуется за счет того что обработанные элементы удаляются, в общем с external sort такой финт не пройдет

в статье даже слова такого нету - inplace

читай внимательней:

It avoids the need for the auxiliary space, and becomes a simple, reliably O(N log N) sorting algorithm.

там есть и пример, сам проверь: listsort.c

вы не видите разницы между «не требует дополнительной памяти» и «сортировка на месте(inplace)»?

а тут моя реализация того же алгоритма: lsort.c, она попроще и покороче

в данном контексте я и в самом деле разницы не вижу, ибо дополнительная память не аллоцируется и ни что ни куда не копируется, а идёт просто жонглированиями поинторами с элементами исходного списка.

у вас какое-то своё особенное определение inplace? будьте добры — обьясните, что вы имеете тогда ввиду.

А дополнитеьлная память не требуется за счет того что обработанные элементы удаляются

неверно

Что бы понять разницу попробуйте слить каким-либо алгоритмом последовательности в 10Gb(которые расположены на диске, в одном файле, первая, потом вторая). Особенно детально рассмотрите тот случай, когда все элементы второй последовательности меньше всех элементов первой последовательности.

- Remove that element, e, from the start of its list, by advancing p or q to the next element along, and decrementing psize or qsize. - удаляем элемент из исходного списка

- Add e to the end of the list L we are building up. - вставляем элемент в конец нового списка

Wikipedia sayz:

In computer science, an in-place algorithm (or in Latin in situ) is an algorithm which transforms input using a data structure with a small, constant amount of extra storage space. The input is _usually_ overwritten by the output as the algorithm executes.

тобиш под это определение поподают как алгоритмы переписывающие входной поток (как вам хочется), так и этого не делающие (мой пример), главное что бы обьём используемой памяти при сортировке был константен (и мал).

посему очевидно, что ваше определение inplace, к сожелению неверно.

an algorithm which transforms input

к чему тут слово usually, не понятно. Суть в том что результат помещается на место исходных данных, и делается за констатнтное место. Ваш алгоритм под это определение не подходит(попробуйте реализовать мой пример).

не согласен, читаем дальше там же:

An algorithm is sometimes informally called in-place as long as it overwrites its input with its output. In reality this is _not sufficient_ (as the case of quicksort demonstrates) _nor is it necessary_; the output space may be constant, or may not even be counted, for example if the output is to a stream.

quicksort как раз перезаписывает входной массив. И в вашем алгоритме не получится за констатное дополнительное пространоство слить две последовательности(см мой пример)

к тому же не вижу противоречия — место константно но не равно нуль, что прекрасно подходит под определение. вы же желаете не использовать дополнительное место совсем. для этого есть другие алгоритмы.

почему?

ок, с таким определением согласен(с константным местом). Но все же inplace логичнее относить к переписыванию входного потока.

к сожалению ваше утверждение не верно. ознакомьтесь ещё раз с алгоритмом.

данные при сортировке ни куда не перемещаются, используется один список поитеров константкой длины N по количеству элементов в списке.

итого потребляемая память: input + output + sizeof(void *) * N. и вы утверждаете, что оно не константно? o_O

Хотя конечно это довольно странная классификация, к тому-же на странице в вики есть только две ссылки на статьи. И подобного определения я нигде до этого не встречал, поэтому вопрос о подобной классификации еще не закрыт

а список поинтеров длинны N - это не дополнительная память. Если у меня есть 100 милионов записей в файле, мне надо будет заводить список из 100 милионов поинтеров для вашего алгоритма? Может при работе над списками этот алгоритм и имеет постоянное место, но вы вобще читали исходный вопрос? Там упоминаются массивы, и внешняя сортировка.

И подобная наивная реализация слияния не пойдет(вместо списков вобще можно подставить любую структуру).

вопрос был про Merge Sort с O(1) по месту. я вам предоставил частное решение и пример для списков, что вполне пересекается с вашим исходным вопросом. в чём проблема то?

> Есть ли слияние с O(1) дополнительной памятью, и более-менее приспособленое для внешней сортировки?

Ваш алгоритм подходит _только_ для списков. Для массивов он не работает.

и работает только благодаря свойствам списков, не более. Алгоритмы слиняния за O(1) дополнительной памяти для массивов сложнее этого алгоритма.

кстати если использовать этот алгоритм для списков, появится как раз O(N) дополнительного места(для указателей).

конечно же я имел ввиду для массивов

ну так переведите массив в список. всё таки дополнительное место под указатели гораздо меньше чем место под данные.

пример для 100 милионов - мне выделить дополнительно 100 милионов указателей для слияния? это получается 381 мегабайт в RAM, зачем, если есть эффективные алгоритмы слияния на месте? Да и место под указатели совсем не гораздо меньше чем под данные. Пример - сортировка целочисленных ключей, в которых данные - 4 байта на ключ. Да и масштабироваться такой алгоритм не будет

в общем, заканчиваем спорить - ваш алгоритм для внешней сортировки не годится, тем более что я уже нашел нужные алгоритмы

тем более что вы сами согласились с тем что ваш алгоритм требует O(N) дополнительного места(в виде указателей). А маленькое потребление, или не маленькое не особо волнует.

да ради бога ;)

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

если же они исходно в этом формате (для чего собственно этот алгоритм и создовался), то ни какой дополнительной памяти не нужно.

нет, см. пост выше

этот алгоритм отличается от самого обычного слияния только удалением элемента из списка после его добавления в результат:)

ну а если данные в виде бинарного дерева, их даже сортировать не надо! Бац, и все! За время O(1) и место O(1):)

ладно, надоело мне спорить ж) но где ты там удаление увидел — для меня загадка