It has a O(n2) time complexity, which makes it inefficient on large lists, and generally performs worse than the similar insertion sort.

Selection sort is noted for its simplicity and has performance advantages over more complicated algorithms in certain situations, particularly where auxiliary memory is limited.

The algorithm divides the input list into two parts: a sorted sublist of items which is built up from left to right at the front (left) of the list and a sublist of the remaining unsorted items that occupy the rest of the list.

The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.

In this case it is more common to remove the minimum element from the remainder of the list, and then insert it at the end of the values sorted so far.

Finding the next lowest element requires scanning the remaining

Therefore, the total number of comparisons is By arithmetic progression, which is of complexity

Insertion sort's advantage is that it only scans as many elements as it needs in order to place the

It can be seen as an advantage for some real-time applications that selection sort will perform identically regardless of the order of the array, while insertion sort's running time can vary considerably.

Selection sort can be implemented without unpredictable branches for the benefit of CPU branch predictors, by finding the location of the minimum with branch-free code and then performing the swap unconditionally.

Finally, selection sort is greatly outperformed on larger arrays by

Heapsort has been described as "nothing but an implementation of selection sort using the right data structure.

"[1] It greatly improves the basic algorithm by using an implicit heap data structure to find and remove each lowest element in

This requires three comparisons per two items (a pair of elements is compared, then the greater is compared to the maximum and the lesser is compared to the minimum) rather than regular selection sort's one comparison per item, but requires only half as many passes, a net 25% savings.

Selection sort can be implemented as a stable sort if, rather than swapping in step 2, the minimum value is inserted into the first position and the intervening values shifted up.

However, this modification either requires a data structure that supports efficient insertions or deletions, such as a linked list, or it leads to performing

After an initial pass to find the greatest value, subsequent passes move every item with that value to its final location while finding the next value as in the following pseudocode (arrays are zero-based and the for-loop includes both the top and bottom limits, as in Pascal): Thus, if on average there are more than two items with the same value, bingo sort can be expected to be faster because it executes the inner loop fewer times than selection sort.