The sort something is to arrange that something into some order.

• sort laundry
• sort out things
• sort a list
• sort an array representing a list

Why is sorting important?

Many algorithms are not practical in the sense that they must look at every possible permutation in order to determine an (optimum) result.

The number of permutations of 60 elements is about the number of seconds in 15 billion years.

In the case of sorting, however, implicit information can be retained during the sorting process to simplify work as the algorithm progresses. A general pseudo code algorithm that can be used to sort a list is as follows.

Here is the pseudo code for a general sorting algorithm.

A sort is stable if, when re-sorted on multiple keys, sorting on a subkey does not change the order of the sort in regards to any more primary key.

A compromise between selection sort and insertion sort is called heap sort. It is much faster on large lists, but is too complicated to introduce at this time.

Heap sort is an unstable sort.

A fast sort, in general, is quick sort, developed by Edsger Dijkstra in the 1960's.

• Make the selection easy and insertion hard: insertion sort
• Make the selection hard and insertion easy: selection sort
• Make a compromise between the two: heap sort
• Impractical sort not recommended: bubble sort.

Only insertion sort is stable, so it is the preferred sort for lists less than size 50 or so.

Let us now look at some implementations of this algorithm.

In the body of the loop, we must select an element from the unsorted list and insert it into the sorted list. If the selection is the more expensive operation, then the sort is called selection sort. If the insertion is the more expensive operation, then the sort is called insertion sort.

In all cases, we will represent the unsorted and sorted lists with an array. Since every time we select an element from the unsorted list, we insert it into the sorted list, we can use the same array to represent both lists at the same time (lists do not always have to start as position 1 in an array). We will use the shorthand notation

Selection sort keeps picking the minimum (or maximum valued item from the unsorted list and adds it to the sorted lists, which is initially empty, until the list is sorted. Selection sort is often used by elementary school teachers in lining up students, by height, to have their picture taken. The pseudo code algorithm for selection sort may be expressed as follows.

Insertion sort keeps picking an item from the unsorted list and inserts it into its proper position in the unsorted list, which is initially empty, until the list is sorted. Many card players use insertion sort when picking up cards, one at a time, and inserting each card into its proper position in the hand, according to the players own ordering preference. The pseudo code algorithm for insertion sort may be expressed as follows.