Алгоритм сортировки - помогите убогому :(

Постарайся развернутее описать свой вопрос. Я 2 минуты перечитывал, так нечего не понял.

Алгоритм. Внешней сортировки простым слиянием. Сортировка есть такая - простым слиянием, внешняя. Элементарно реализуется если размер сортируемого массива данных 2^n. Могу описать сам алгоритм...

Или не простым, а прямым слияением?...

http://en.wikipedia.org/wiki/Merge_sort читали?

anonymous (*) (05.06.2006 16:48:03):

> Сортировка есть такая - простым слиянием, внешняя.

Хоть на анлийском бы написАл...

У меня, например, ничего не шевельнулос... Merge sorting, как я понимаю, не то?

А "внешняя" -- "external", или как?

> если произвольный размер массива?

делишь пополам, если нечётное -- почти напополам, если единица -- уже отсортировано. сортируешь половинки рекурсивно, сливаешь взад.

в чём проблема-то?

Внешняя сортировка - это сортировка без загрузки всего массива в память, когда для этого там просто нет места.

http://iclub.nsu.ru/~andy/Lectures/ExternalSearch.html

2bbk123:

> http://iclub.nsu.ru/~andy/Lectures/ExternalSearch.html

В Высшей Степени Научно! Если ты разрабатываешь драйве для файлухи, или СУБД на raw девайсах оно, конечно, не совсем глупо, хотя и тривиально...

На практике же ты имеешь дело с кэшированием/буферизацией с последующим рескедьюлингом как на уровне операционки, так и на уровне контроллеров, а все 2*P девайсов объединены в (страйпнутый) райд.

Имеется много реализаций split'n'merge для случаев, когда данные не влезают в память. Собственно, почти все реализации сортировки данных, не влазающих в память, основанны на split'n'merge.

По моим наблюдениям,

1. Оптимальнее всего сливать не P ветвей, а 2. Мало того, при P>2 на достаточных объемах данных (начиная уже с сотен гигабайт) получаются проблемы, особенно под RaiserFS.

2. Буферизация необходима, но сортировку лучше отделять от буферизации.

Насчет оригинального вопроса:

Не понял проблему...

Если последняя запись короче M, то и Бог с ним, пусть будет короче M. Хоть бы и 1 -- она, кстати, уже и отсотрирована будет...

Если вдруг все влезло, игнорируешь оставшиеся свободные устройства.

Если на каком-либо устройстве записей больше нет, исключаешь его из слияния.