Merge sort и AS3. Обгоняем родной Vector.sort(Array.NUMERIC)

[ImLiar]

я на флэше не пишу, но мне все же интересно — а часто вам приходится сортировать 75 миллионов элементов в actionscript?

[richtrr]

1000 * 75000 != 75000000 ?

[valemak]

Обожаю хабрастатьи про сортировки, но, извините, я не уследил за ходом Вашей мысли.
Кому именно родная «родная сортировка»? )))

[krati]

экземплярам Vector'а(типизированный массив в as3).

new [3, 1, 4, 2, 5].sort(Array.NUMERIC);

короче native sort

[Seldon]

Имхо, для того. чтобы читателям статьи было интересно её читать, неплохо было бы указать какой именно алгоритм применяется в этой «native sort».
Во вторых конечно же нужно понимать с какими данными мы работает, что ожидаем ибо существует огромное количество сортировок и каждая дает плюс в своей области.

Родная сортировка требует примерно n*1.5 дополнительной памяти, mergeSort — ровно n.

откуда информация, как сравнивали?

И имхо в вашем случе было бы проще использовать quicksort, для массивов уж точно. mergeSort для структур даных с послеовательным доступом да и запускать его намного лучше скажем в 2 4 8 и тд потоках когда у вас реально есть 100 миллионов записей и есть 8 ядер процессора, а рузультат нужен вчера и конечно же пропускная способность дисков и памяти позволит нагрузить все 8 ядер.

[krati]

память определял на глаз, смотрел сколько плеер съедает памяти.
на 20 миллионов native sort — 246940kb, mergeSort — 168656kb.
168656 / (((20000000*32)/8/1024)*2) = 1.08
246940 / (((20000000*32)/8/1024)*2) = 1.58

случайный массив делается

result[i] = Math.random() * length + .5 | 0;

какой алгоритм в native sort — я хз, не смог найти.
например по ссылке в комменте habrahabr.ru/post/207784/#comment_7154708 — в статье говорят — пузырьком, в комментах — quicksort

[Aquahawk]

Если хотите извращений, возьмите ещё вот эту штуку да погоняйте someideas.ru/2011/06/11/быстрая-сортировка-на-as-3-0/

[Aquahawk]

А ещё, приведите пожалуйста оригинальный код который вы использовали для вызова родной сортировки. Там тоже фокусы могут быть.

[krati]

простейший код,

var a:Vector.<int> = getArray(length);
var time:Date = new Date();
a.sort(Array.NUMERIC);

[richtrr]

vector.sort() реально тормозной я использовал сортировку Шелла
artman.fi/2009/06/as3-sorting-algorithm-faster-than-native-sorting/
Работает всегда быстрее, на частично отсортированных данных быстрее в разы
Попробую ваш вариант