Алгоритмизация. Сортировка вставкой, Сортировка слиянием.

Сортировка вставкой - эффективна при небольших объемах данных. Время выполнения - с1 * n^2, где c1 - некая константа не зависящая от n, характеризуется качеством программиста (чем лучше программист тем меньше эта константа), языком программирования (чем более низкоуровневый язык программирования тем меньше эта константа), компилятором (чем лучше компилятор тем меньше эта константа), короче количество инструкций переданных процессору для выполнения этого алгоритма (чем меньше тем лучше). n - количество элементов поступивших на сортировку (количество сортируемых элементов массива).

Сортировка слиянием - эффективней чем сортировка вставкой при больших объемах данных. Время выполнения - c2 * n * log2 n, где c2 - некая константа не зависящая от n, характеризуется качеством программиста (чем лучше программист тем меньше эта константа), языком программирования (чем более низкоуровневый язык программирования тем меньше эта константа), компилятором (чем лучше компилятор тем меньше эта константа), короче количество инструкций переданных процессору для выполнения этого алгоритма (чем меньше тем лучше).
n - количество элементов поступивших на сортировку (количество сортируемых элементов массива).

Что бы посчитать время выполнения алгоритма методом вставки для миллиона элементов, предположим что использовался низкоуровневый язык программирования, хороший компилятор, и крутой программист, тогда c1 = 2 (допустим), а скорость работы компьютера миллиард команд в секунду, получаем такую формулу для алгоритма вставки:
                                        (2 * (10^6)^2)/10^9 = 2000с
                                                                 10^6 это миллион (количество элементов)
                            10/9 это миллиард (количество инструкций в секунду)

Что бы посчитать время выполнения алгоритма методом замены для миллиона элементов, предположим что использовался высокоуровневый язык программирования, плохой программист, плохой компилятор тогда c2 будет большой c2 = 50 (допустим), а скорость компьютера 10 миллионов инструкций в секунду, получаем такую формулу для алгоритма замены:                                           (50 * 10^6 * log2 10^6) / 10^7 = 100 (прибл)
                                                                10^6 это миллион (количество элементов)
                            10^7 это 10 млн (количество инструкций в секунду)
                            log2 10^6 = 19.93
Реализация алгоритма сортировки вставкой
//Sort insertion по возрастанию
private function sortInsertion(array:Array):void{
    var n:int = array.length;
    for (var j:int = 1; j < n; j++){
        //Запоминаем чилсло которое будем премещать направильную позицию
        var key:int = array[j];
        //Получаем индекс числа стоящий перед чилсом котороу будем перемещать
        var i:int = j - 1;
        //Если число которое будем перемещать меньше чем перед ним стоящее начинаем сортировать массив
        while (i > -1 && array[i] > key){
            array[i + 1] = array[i];
            i--;
        }
        //В конце концов ставим сортируемое чилсо на правильную позицию
        array[i + 1] = key;
    }
}