Sorting Algorithms

Insertion Sort

Sorts a list by placing each element in the position it should be in and gradually adding more elements one by one., A sort in which each item in a set is inserted into its proper position in the sorted set according to a specified criterion.

Selection Sort

Sorts a list by searching for the 1st element, then the 2nd, and so on until all the elements are in place., A sort in which the items in a set are examined to find an item that fits specified criteria. This item is appended to the sorted set and removed from further consideration, and the process is repeated until all items are in the sorted set.

Bubble Sort

A sort in which the first two items to be sorted are examined and exchanged if necessary to place them in the specified order; the second item is then compared with the third (exchanging them if required), the third is compared with the fourth, and the process is repeated until all pairs have been examined and all items are in the proper sequence.

Quicksort

A sort in which a list is first partitioned into lower and upper sublists for which all keys are, respectively, less than some pivot key or greater than the pivot key. See also the definitions for "bubble sort", "selection sort" and "insertion sort".

Mergesort

Splits the list into sub-lists and then reconstructs the original list.

Heap sort

This algorithm is based on the heap data structure, and is a more efficient version of selection sort. It determines the largest element. Then, it places that element at the end (or beginning) of the list, and then repeats the process with the rest of the list Recall that in a heap, the top element of the heap is always "next" in order (either the next highest or next lowest, in the case of numbers). If you were to take all of your input values and store them in a heap, and remove one element at a time, the elements will be removed in sorted order. Depending on the data list being sorted, this could have performance consequences. Heap sort is considered an "instable" sort because it doesn't preserve the original order of equal elements.

Stable sort

Any sort method that does not change the order of equal-rank elements.

Comparison sort

A sort that ranks items by comparing them to each other. As opposed to a sort that uses some other method, like the radix sort that analyzes the bits of each number.

Insertion sort time complexity

O(n^2) worst case, O(n) best case

Heap sort time complexity

O(n log n) in all cases

Quicksort time complexity

O(n^2) in the very unlikely worst case, O(n log n) in other cases

Selection sort time complexity

O(n^2) in all cases

Bubble sort time complexity

O(n^2) worst case, O(n) best case

Mergesort time complexity

O(n log n) in all cases