Selection sort is a simple sorting algorithm done by comparison. The time complexity of selection sort is O(n²) for an array containing n elements. Thus, it is quite an inefficient means of sorting for large data sets. Nevertheless, it is a very intuitive algorithm, and it has certain benefits.

Selection sort is a particularly useful when the data set is a small list of elements, and when memory is limited. It is considered an "in-place" algorithm, which means that no additional storage is needed to complete the sort. The sort is done within the array that holds the original list.

The Algorithm: Similar to insertion sort, we partition the array into a sorted portion and an unsorted portion as we execute the algorithm.

We first compare the element at index i=0 (orange) with every element at index j>i (green). If we find an element at index j that is smaller than the element at index i (and the smallest of all indices j>i) we highlight it red. We then we swap the elements at index i=0 and j. Index 0 will then be a sorted sub array of length 1 (dark blue), with the rest of the array unsorted.

We continue in this pattern, swapping the element at index i=1 with the smallest element at index j>i. The algorithm again continually swaps the next smallest element into the smallest index of the unsorted portion of the array, appending it to the sorted portion of the list.

For an array of size n, once the sorted portion is of size n-1, the last element in the unsorted portion will clearly be in its sorted position, and we then have our entire array sorted.