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

Что бы понять эту сортировку, нужно понять три принципа:

• Сливать нужно только упорядоченные массивы.
• Массив из одного элемента считается упорядоченным.
• Результат слияния — упорядоченный массив.

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

Что бы достаточно хорошо понять алгоритм — надо его реализовать.
У меня получилось так:

function mergeSort(array:Array):Array { 	var chunkSize:int = array.length / 2; 	if(chunkSize >= 1){ 		var left:Array = mergeSort(array.slice(0, chunkSize)); 		var right:Array = mergeSort(array.slice(chunkSize)); 		 		var result:Array = []; 		while(left.length && right.length){ 			if(left[0] < right[0]){ 				result.push(left.shift()); 			} else{ 				result.push(right.shift()); 			} 		} 		return result.concat(left, right); 	} 	return array; }

На самом деле, даже такая реализация быстрее некоторых, найденных мною во всяких блогах.

Рекурсивно, сортируются сначала первые элементы. То есть 0 и 1, потом 2 и 3, потом 0..1 и 2..3 сливаются в один массив 0..3, и только после 4 и 5.
(число перед открывающей скобкой — приоритет)

6{     _3_[         1(1, 2),         2(3, 4)     ],     5[         _4_(5, 6)     ] }

Но можно отсортировать все подмассивы из одного элемента, и потом их сливать в подмассивы из 4 элементов.

6{     _4_[         1(1, 2),         2(3, 4)     ],     5[         _3_(5, 6)     ] }

Это позволяет избавится от рекурсии.

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

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

Короче, рисуем сову:

function mergeSort(array:Vector.<int>):Vector.<int> { 	var length:uint = array.length; 	var buffer:Vector.<int> = new Vector.<int>(length, true); 	for (var leftChunkSize:uint = 1; leftChunkSize < length; leftChunkSize *= 2) { // low 		var bufferPointer:uint = 0; 		var leftChunkStart:uint = 0; 		for (; leftChunkStart < length; leftChunkStart += leftChunkSize * 2) { // mid 			var rightChunkStart:uint = Math.min(leftChunkStart + leftChunkSize, length); 			var rightChunkEnd:uint = Math.min(rightChunkStart + leftChunkSize, length); 			 			var leftChunkEnd:uint = rightChunkStart; 			 			var leftPointer:uint = leftChunkStart; 			var rightPointer:uint = rightChunkStart; 			 			while (leftPointer < leftChunkEnd && rightPointer < rightChunkEnd) { // hard 				if (array[leftPointer] < array[rightPointer]) { 					buffer[bufferPointer++] = array[leftPointer++]; 				}else { 					buffer[bufferPointer++] = array[rightPointer++]; 				} 			} 			while (leftPointer < leftChunkEnd) { // hard 				buffer[bufferPointer++] = array[leftPointer++]; 			} 			while (rightPointer < rightChunkEnd) { // hard 				buffer[bufferPointer++] = array[rightPointer++]; 			} 		} 		 		var temp:Vector.<int> = array; 		array = buffer; 		buffer = temp; 	} 	 	if (result !== array) { 		for (var i:uint = 0; i < length; i++ ) { 			result[i] = array[i]; 		} 	} 	return result; }

Конфигурация ПК: DDR3-1066 2GB, P6200 (2×2.13GHz).
(«FP» читать как «FlashPlayerDebugger 11.9.900.170», release)

Теперь немного оптимизируем узкие места:

• Math.min намного медленнее, чем простыми условиями.
• Побитовый сдвиг быстрее умножения и деления на 2.
• Еще можно вспомнить, что на самом деле делает &&, и избавится от него.

Получаем:

function mergeSort(array:Vector.<int>, buffer:Vector.<int> = null):Vector.<int> { 	var length:uint = array.length; 	var result:Vector.<int> = array; 	buffer = buffer ? buffer : new Vector.<int>(length, true); 	for (var chunkSize:uint = 1; chunkSize < length; chunkSize <<= 1) { 		var bufferPointer:uint = 0; 		var leftChunkStart:uint = 0; 		for (; leftChunkStart < length; leftChunkStart += chunkSize << 1) { 			var rightChunkStart:uint = leftChunkStart + chunkSize; 			var rightChunkEnd:uint = rightChunkStart + chunkSize; 			if (length < rightChunkEnd) { 				rightChunkEnd = length; 				if (length < rightChunkStart) { 					rightChunkStart = length; 				} 			} 			 			var leftChunkEnd:uint = rightChunkStart; 			 			var leftPointer:uint = leftChunkStart; 			var rightPointer:uint = rightChunkStart; 			 			while (leftPointer - leftChunkEnd & rightPointer - rightChunkEnd) { 				if (array[leftPointer] < array[rightPointer]) { 					buffer[bufferPointer++] = array[leftPointer++]; 				}else { 					buffer[bufferPointer++] = array[rightPointer++]; 				} 			} 			while (leftPointer < leftChunkEnd) { 				buffer[bufferPointer++] = array[leftPointer++]; 			} 			while (rightPointer < rightChunkEnd) { 				buffer[bufferPointer++] = array[rightPointer++]; 			} 		} 		 		var temp:Vector.<int> = array; 		array = buffer; 		buffer = temp; 	} 	 	if (result !== array) { 		for (var i:uint = 0; i < length; i++ ) { 			result[i] = array[i]; 		} 	} 	return result; }

10^8 элементов такая реализация у меня сортирует за 47 секунд в PepperFlash.

в случае с полностью отсортированными массивами, обе сортировки работают быстрее(например, при 2 000 000 элементах примерно на 30% быстрее, обе).
Родная сортировка требует примерно n*1.5 дополнительной памяти, mergeSort — ровно n.

В итоге, в FP профита от этих телодвижений мало. А вот в PepperFlash можно наблюдать цифры чуть ли не в двое меньше.