Here is the summarized space and time complexity of the sorting algorithms in best, average, and worst case.
Bookmark this page or save the below image for quick reference, especially for interviews.
n = number of elements in the array k = range of input
Selection sort, insertion sort, merge sort and quick sort are not affected by the range of input.
For details, read basic sorting algorithms.
Interviewers usually ask questions on the complexity of the sorting algorithm to test your algorithm and coding understanding.
Merge sort is considered to be the most efficient sorting algorithm as it takes
O(n log n) time in the best, average, and worst case.
Insertion sort, merge sort, quick sort, and heap sort are some examples of comparison-based sorting algorithms.
Counting sort, radix sort, and bucket sort are some examples of non-comparison-based sorting algorithms.
If the sorting algorithm does not take any extra space, is called an in-place sorting algorithm. The space complexity of the in-place sorting algorithm is
Buble sort, selection sort and insertion sort are examples of in-place sorting algorithms.
Sorting algorithm-related tutorials: