Space and Time Complexity of Sorting Algorithms

Aniruddha Chaudhari
Updated: Dec 03, 2023

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.

Here,

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.

Frequently asked questions in interviews about the complexity of sorting algorithms?

Interviewers usually ask questions on the complexity of the sorting algorithm to test your algorithm and coding understanding.

What is the best and most efficient sorting algorithm?

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.

What are the comparison-based sorting algorithms?

Insertion sort, merge sort, quick sort, and heap sort are some examples of comparison-based sorting algorithms.

What are the non-comparison-based sorting algorithms?

Counting sort, radix sort, and bucket sort are some examples of non-comparison-based sorting algorithms.

What is in-place sorting?

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 O(1).
Buble sort, selection sort and insertion sort are examples of in-place sorting algorithms.

Sorting algorithm-related tutorials:

Aniruddha Chaudhari

I am a Python enthusiast who loves Linux and Vim. I hold a Master of Computer Science degree from NIT Trichy and have 10 years of experience in the IT industry, focusing on the Software Development Lifecycle from Requirements Gathering, Design, Development to Deployment. I have worked at IBM, Ericsson, and NetApp, and I share my knowledge on CSEstack.org.