Please visit, subscribe and share 10 Minutes Lectures in Computer Science

# Data structures and algorithms cheat sheet, sorting algorithms quick reference, comparison of sorting algorithms on auxiliary space used, sorting algorithms cheat sheet, stable vs in-place vs comparison sorting algorithms quick reference

## Sorting algorithms - A comparison

 Algorithm Time complexity Space complexity In-place Stable Comparison No. of comparisons Best Average Worst Total Auxiliary Min Max Bubble sort O(n) O(n2) O(n2) O(n) O(1) Yes Yes Yes n(n-1)/2 n(n-1)/2 Selection sort O(n2) O(n2) O(n2) O(n) O(1) Yes No Yes n(n-1)/2 n(n-1)/2 Insertion sort O(n) O(n2) O(n2) O(n) O(1) Yes Yes Yes n-1 n(n-1)/2 Merge sort O(n log n) O(n log n) O(n log n) O(n) O(n) No Yes Yes n*log 2 n n*log 2 n Quick sort O(n log n) O(n log n) O(n2) O(n) O(1) Yes No Yes n*log2n n(n-1)/2 Heap sort O(n log n) O(n log n) O(n log n) O(n) O(1) Yes No Yes n*log2n n*log2n Bucket sort O(n+k) O(n+k) O(n2) O(n+k) No Yes No Depends on the algorithm used to sort the elements in each bucket Radix sort O(nk) O(nk) O(nk) O(n+k) Yes Yes No NA Shell sort O(n log n) O(n log2n) O(n log2n) O(n) O(1) Yes No Yes n*log2n

Notations used

• n refers to number of elements to be sorted.
• k in Bucket sort refers to number of buckets, in Radix sort refers to the maximum length of the input elements.

Auxiliary Space

is the temporary space allocated by your algorithm to solve the problem, with respect to input size.

Space Complexity

is the total space used by your algorithm to solve the problem, with respect to input size. Note that the Space Complexity includes input size.

In-place sorting algorithm

A sorting algorithm is in-place if it requires only O(1) extra space to sort the array.

Stable sorting algorithm

We say that a sorting algorithm is stable if, when two records have the same key, they stay in their original order. A sort is stable if two elements with the same value maintain their same relative order before and after the sort is performed.

Comparison sorting algorithm

Any sort algorithm using comparisons between keys (elements), and nothing else about the keys, to arrange items in a predetermined order (ascending or descending). The predetermined sorted order is determined by a sequence of comparisons between pairs of elements.

********************