Insertion Sort

Back when computers were running in the one megahertz and less range, making code for a program extremely efficient was one of the most important factors to users. A program that ran slowly and took up much of the resources did not appeal to the user. Today computers run up to two gigahertz and above range, thus speed and efficiency are almost irrelevant. Yet, back in the stone age of computers efficiency was very important. Thus, computer programmers derived algorithms that could sort information. This lead to the formation of the bubble sort, heap sort, merge sort, quick sort, binary tree sort, pigeonhole sort, radix sort, insertion sort and many others. Different individuals or groups attempted to create a sorting algorithm that would be more efficient than the rest. Some became excellent sorters while others were not as proficient.

Sorting algorithms were measured by a standard called big O. Big O measures algorithms by taking the worst-case that the algorithm could have and timing it. An official definition of big O is, “Algorithm A is order f(n) denoted O(f(n)) if constants k and n(initial) exist such that A requires no more than k * f(n) time units to solve a problem size n >= n(initial)”. This is a very confusing definition taken from the book currently used in ICS 211. The time the algorithm took would then be recorded as an algebraic expression. The big O time would look like this: O(n), with “n” being the algebraic number. All big O expressions could be drawn on a graph. The big O expressions ranged from the exponential big O O(2^n), which is the longest to the constant O(1), which is the fastest. The big O begins with the constant with is O(1). This is the fastest measurement. This means the at worst the algorithm would take only 1 regardless of the size. The next fastest is the log (log n). This cuts the algorithm in half and solves it in half the time of an “n” algorithm. The next fastest is the linear big O or O(n). An example of this is a while or for loop or doing a sequential search for data in an array or linked list. Regardless of the size of the contents within the for or while loop the O(n) remains the same because it measures the worst-case. The same principal is applied to all the big O’s. The next fastest is the log O(n log n). This is slower than O(n) because you multiply the “n” by a log n. This big O increases more rapidly than linear algorithms but not as fast as quadratic ones. Next is the quadratic big O, O(n^2). An example of this is a nested loop. The exponential big O, O(2^n) is the slowest algorithm of all.

At worst-case insertion sort’s big O is O(n^2). This is slow compared to other algorithms such as heap sort, which is O(n log n) and merge sort, which is also O(n log n). Still insertion sort is comparable to bubble sort, quick sort, and binary tree sort at worse. When comparing average-case scenarios, insertion sort still has a big O of O(n^2). All the other sorts big O remain the same except for quick sort and binary tree sort. The big O for these decreases to O(n log n). So as you can see quick sort and merge sort are normally faster than insertion sort. The only time insertion sort is faster than quick sort and merge sort is during the best-case scenario. When the array is already sorted then the big O of insertion sort is only O(n). Merge sort and quick sort stay at O(n log n). This means that the only time insertion sort is fast is when the array or list is sorted and that defeats the purpose of the sorting algorithm.

Insertion sort works by inserting each value of an unsorted section into a sorted section of a list or array. Each time the algorithm will take the first number in the unsorted section and add them into the sorted section in the appropriate position. It will go through the array or list until it adds all the unsorted numbers into the sorted section. An example often used when trying to understand insertion sort is sorting a deck of cards. You begin by picking one card and insert it into the proper position. As you go through the cards the sorted section becomes larger and the unsorted section becomes smaller until all the cards are sorted. If the cards are already sorted when you get them you do one scan of the cards and leave them alone. This is the best case that could happen and that is why at best the big O is just O(n). Having the cards all the cards sorted is highly unlikely to occur. Insertion sort works well only if the array of list is almost sorted. If the array or list is long and sorted backwards then insertion sort will take an extremely long time to sort everything. If insertion sort is still confusing then visit this page, http://al.ei.tuat.ac.jp/~sekisita/isort-e.html. This page contains an animation of insertion sort using bars.

A man named Shell created a sorting algorithm called the Diminishing-Increment Insertion Sort, also known simply as Shell Sort. He tried to create a sorting algorithm that had the advantages of insertion sort but none of the drawbacks. Shell sort works by taking the number within the array or list in increments of 5, 3 and 1. For example it would take every 5 numbers first and sort them using insertion sort. Then it would move to the ones next to each 5 and sort those. After that it would do the same, except in increments of 3 and then 1. At 1 it would finish sorting the array or list. The increments can be any reasonable number as long as the last one is 1. Unfortunately shell sort is only O(n^1.5) at worst and on average O(n^1.25). This is better than insertion sort but there are many other sorts that are faster. Below is a table displaying how inefficient insertion sort can be when compared to shell sort and quick sort, which are variants of insertion sort.

count	insertion	shell	quicksort
16	39 µs	45 µs	51 µs
256	4,969 µs	1,230 µs	911 µs
4,096	1.315 sec	.033 sec	.020 sec
65,536	416.437 sec	1.254 sec	.461 sec

        for (j = 2; j < A.length; j++){
            key = A[j];
            //Insert A[j] into the sorted sequence A[1...j-1]
            i = j - 1;
            while((i > 0) && (A[i] > key)) {
                A[i+1] = A[i];
                i = i - 1;
            }//end while loop
            A[i+1] = key;
        }//end for loop
    return A;
}

Frank M. Carrano, Janet J. Prichard. “Data Abstraction and Problem Solving with Java.” Addison Wesley, San Francisco, 2001, pgs. 390-393