3.1 INSERTION SORT 59
ing these two. Quicksort is a recursive sort that picks a pivot element from the
list and then subdivides the list into two parts that contain the elements that are
smaller and larger than the pivot.
The last sort considered is different in that it works with lists that are so large
that they cannot be reasonably held in a computer’s memory all at once. This
external sort works with groups of records in sequential files and is designed to
limit the file accesses, which would be an operation much slower than a com-
parison. The reader should note that even with expanded memory in today’s
computers, holding all of a database’s records in memory at once may be possi-
ble but may incur delays due to virtual memory swapping. In this case, even
though writing to disk files is not part of the algorithm, the reliance on virtual
memory incurs the same cost because swaps are written to temporary disk files
by the operating system.
3.1 Insertion Sort
The basic idea of insertion sort is that if you have a list that is sorted and need
to add a new element, the most efficient process is to put that new element
into the correct position instead of adding it anywhere and then resorting the
entire list. Insertion sort accomplishes its task by considering that the first ele-
ment of any list is always a sorted list of size 1. We can create a two-element
sorted list by correctly inserting the second element of the list into the one-
element list containing the first element. We can now insert the third element
of the list into the two-element sorted list. This process is repeated until all of
the elements have been put into the expanding sorted portion of the list.
The following algorithm carries out this process:
InsertionSort( list, N )
list the elements to be put into order
N the number of elements in the list
for i = 2 to N do
newElement = list[ i ]
location = i - 1
while (location ≥ 1) and (list[ location ] > newElement) do
// move any larger elements out of the way
list[ location + 1] = list[ location ]
location = location - 1
