Сортировка вставкой

[whoElse]

Начал изучать алгоритмы. Дело идёт туговато, но идёт. Первый же алгоритм из книги Кормена - как он должен выглядеть в идеале? Кто-то может объснить, почему первый алгоритм работает быстрее второго? Какие допущены ошибки?

var array = [25, 146, 33, 228, 1047, 5, 87, 556];
	
	
	function insertion_sort(arr) {
		var date1 = new Date;
		for (var x=1; x < 1000000; x++) {
		for (var j=1; j <= arr.length-1; j++) {
			var key = arr[j];
			var i = j - 1;
			while (i >= 0 && arr[i] > key) { // i >= 0 ne nado?
				arr[i+1] = arr[i];
				i--;
			}
			arr[i+1] = key;
		}

	}
			var date2 = new Date;
			alert(date2 - date1);
			alert(arr);
	}

	
	insertion_sort(array);
	
	function insertionSort(items) {
	var date1 = new Date;
	for (var x=1; x < 1000000; x++) {

    var len     = items.length,     // number of items in the array
        value,                      // the value currently being compared
        i,                          // index into unsorted section
        j;                          // index into sorted section
    
    for (i=0; i < len; i++) {
    
        // store the current value because it may shift later
        value = items[i];
        
        /*
         * Whenever the value in the sorted section is greater than the value
         * in the unsorted section, shift all items in the sorted section over
         * by one. This creates space in which to insert the value.
         */
        for (j=i-1; j > -1 && items[j] > value; j--) {
            items[j+1] = items[j];
        }

        items[j+1] = value;
    }
			
    
}
			var date2 = new Date;
			alert(date2 - date1);
			alert(items);
}
insertionSort(array)

[rgl]

А что вы хотите таким способом замерить? Вы один раз сортируете массив, а потом 999998 раз напускаете вашу функцию на уже отсортированный массив.

[rgl]

while (i >= 0 && arr[i] > key) { // i >= 0 ne nado?

Как это не надо? Оно вроде бы и работает без этого, но это фишка JavaScript, что undefined > любоечисло возвращает false. На других языках последствия могут быть непредсказуемы. Да и на JavaScript тоже нехорошо, попробуйте напр. с такими данными:
var array = [25, 146, 33, 228, 1047, 5, 87, 556];
array[-1] = 100;