Insertion Sort

Monday, June 21, 2010 by gradbot

Insertion sort works by iterating over a list once starting from the left. It looks at each element and the previous element swapping them if they are out of order and it keeps swapping the same element, moving it left, until the comparison is correct or it is in the first position. Wikipedia on Insertion sort.

An interesting thing about insertion sort is that it often runs faster than many θ(n log n) algorithms for small datasets, 8-20 elements, even though its worse case runtime is θ(n^2).



algorithms.sort.insertion = function(array, predicate){
    var length = array.length;
    for (var start = 1; start < length; start++) {
        var i = start;
        do {
            if (predicate(array, i, i - 1)) {
                array.swap(i, i - 1);
            } else {
                break;
            }
            i--;
        } while (i);
    }
};

Filed under , , , having