We'll study and compare roughly seven sorting algorithms. We employ a list S, and maintain the invariant that S is sorted. Start with an empty list S and the unsorted list I of n input items. S may be an array or a linked list. If S is an array, one of the nice things about insertion sort is that it's an in-place sort.
Selection sort is equally simple, and also quadratic.
Again we employ a list S, and maintain the invariant that S is sorted. Now, however, we walk through I and pick out the smallest item, which we add to the end of S. Start with an empty list S and the unsorted list I of n input items. Heapsort is a selection sort in which we use a heap to do the selecting. Start with an empty list S and an unsorted list I of n input items. Extra memory is used by this array.