The algorithm finds the minimum value, swaps it with the value in the first
position, and repeats these steps for the remainder of the list. It does no more
than *n* swaps, and thus is useful where swapping is very expensive.

*Insertion sort* is a simple sorting algorithm that is relatively
efficient for small lists and mostly sorted lists, and often is used as part of
more sophisticated algorithms. It works by taking elements from the list one by
one and inserting them in their correct position into a new sorted list. In
arrays, the new list and the remaining elements can share the array's space, but
insertion is expensive, requiring shifting all following elements over by one.

*Merge sort* takes advantage of the ease of merging already sorted lists
into a new sorted list. It starts by comparing every two elements (i.e., 1 with
2, then 3 with 4...) and swapping them if the first should come after the
second. It then merges each of the resulting lists of two into lists of four,
then merges those lists of four, and so on; until at last two lists are merged
into the final sorted list. Of the algorithms described here, this is the first
that scales well to very large lists, because its worst-case running time is
O(*n* log *n*). Merge sort has seen a relatively recent surge in
popularity for practical implementations, being used for the standard sort
routine in the programming languages Perl,^{[7]} Python (as timsort^{[8]}), and Java (also uses timsort as of JDK7^{[9]}),
among others. Merge sort has been used in Java at least since 2000 in
JDK1.3.^{}^{}

*Heapsort* is a much more efficient version of selection sort. It also works by determining the
largest (or smallest) element of the list, placing that at the end (or
beginning) of the list, then continuing with the rest of the list, but
accomplishes this task efficiently by using a data structure called a heap, a
special type of binary tree.
Once the data list has been made into a heap, the root node is guaranteed to be
the largest (or smallest) element. When it is removed and placed at the end of
the list, the heap is rearranged so the largest element remaining moves to the
root. Using the heap, finding the next largest element takes *O(*log
*n)* time, instead of *O(n)* for a linear scan as in simple selection
sort. This allows Heapsort to run in *O(n* log *n)* time, and this is
also the worst case complexity.

*Quicksort* is a divide and conquer algorithm which relies on a
*partition* operation: to partition an array an element called a
*pivot* is selected. All elements smaller than the pivot are moved before
it and all greater elements are moved after it. This can be done efficiently in
linear time and in-place. The lesser and greater sublists
are then recursively sorted. Efficient implementations of quicksort (with
in-place partitioning) are typically unstable sorts and somewhat complex, but
are among the fastest sorting algorithms in practice. Together with its modest
O(log *n*) space usage, quicksort is one of the most popular sorting
algorithms and is available in many standard programming libraries. The most
complex issue in quicksort is choosing a good pivot element; consistently poor
choices of pivots can result in drastically slower O(*n*²) performance, if
at each step the median is chosen as the
pivot then the algorithm works in O(*n* log *n*). Finding the median
however, is an O(n) operation on unsorted lists and therefore exacts its own
penalty with sorting.

Counting sort is applicable when each input is known to belong to a
particular set, *S*, of possibilities. The algorithm runs in O(|*S*| +
*n*) time and O(|*S*|) memory where *n* is the length of the
input. It works by creating an integer array of size |*S*| and using the
*i*th bin to count the occurrences of the *i*th member of *S* in
the input. Each input is then counted by incrementing the value of its
corresponding bin. Afterward, the counting array is looped through to arrange
all of the inputs in order. This sorting algorithm cannot often be used because
*S* needs to be reasonably small for it to be efficient, but the algorithm
is extremely fast and demonstrates great asymptotic behavior as *n*
increases. It also can be modified to provide stable behavior.

Bucket sort is a divide and conquer sorting
algorithm that generalizes Counting sort by partitioning an array into a
finite number of buckets. Each bucket is then sorted individually, either using
a different sorting algorithm, or by recursively applying the bucket sorting
algorithm. A variation of this method called the single buffered count sort is
faster than quicksort.^{}

Due to the fact that bucket sort must use a limited number of buckets it is best suited to be used on data sets of a limited scope. Bucket sort would be unsuitable for data such as social security numbers - which have a lot of variation.

*Radix sort* are algorithms that sort numbers by processing individual
digits. *n* numbers consisting of *k* digits each are sorted in
O(*n* · *k*) time. Radix sort can process digits of each number either
starting from the least significant digit (LSD) or
starting from the most significant digit (MSD). The LSD
algorithm first sorts the list by the least significant digit while preserving
their relative order using a stable sort. Then it sorts them by the next digit,
and so on from the least significant to the most significant, ending up with a
sorted list. While the LSD radix sort requires the use of a stable sort, the MSD
radix sort algorithm does not (unless stable sorting is desired). In-place MSD
radix sort is not stable. It is common for the counting sort algorithm to be used internally by
the radix sort. Hybrid sorting approach, such as using insertion sort for small bins improves
performance of radix sort significantly.