Sorting algorithms are very important algorithms in computer science. Having a good grasp of sorting algorithms is necessary to solve complex problems. Learning the time and space complexity of different Sorting algorithms helps you decide which sorting algorithm is best for the given problem.

In this article, we will discuss the space and time complexity of sorting algorithms: Selection Sort, Insertion Sort, Bubble Sort, Merge Sort, Quicksort, Heap Sort, Counting Sort, Radix Sort, and Bucket Sort.

What is Time Complexity?

The amount of time an algorithm takes to run based on the input size is known as time complexity. In computer science, a problem can be solved using different algorithms. Some algorithms may be high-speed, and some may be very slow. We must find out the fastest and most efficient algorithm to save time to solve the problem. To find out the fastest algorithm, we must understand the time complexity.

What is Space Complexity?

Space Complexity is the measure of memory consumed by a program to operate on the input of a given size. Hence, Space complexity is essentially the sum of the Auxiliary memory used and the memory used by input. However, this definition isn’t popularly used for comparing algorithms; otherwise, the space complexity of bubble and merge sort would be the same as O(n). This is why it’s best to say that certain algorithms like bubble sort require O(1) extra memory, and merge sort requires O(n) extra memory when discussing algorithms' complexity analysis.

Why Are Time and Space Complexities Important?

Time and space complexities are important because they tell us how fast a program runs and how much memory it uses.

Think of it like this: when you're cooking a meal, you want to know how long it will take (time complexity) and how much space you need on your counter and in your plates (space complexity).

Time complexity gives us an idea of how the time to run a program increases as the amount of data it deals with grows. For example, a program might take 5 minutes to sort 100 names, but 50 minutes to sort 10,000 names. Knowing this helps programmers choose the fastest algorithms for their needs.

Space complexity is about how much memory a program needs to work. If a program needs a lot of memory, it might not run well on a phone or a small computer.

Both are important because they help us make programs that run efficiently, without wasting time or memory. This is crucial for creating good software, especially for apps and systems that handle lots of data or need to work very fast.

Types Of Time Complexity

Best Time Complexity

This refers to the minimum amount of time that an algorithm requires to execute for a given input size under ideal conditions. It represents the fastest execution time achievable by the algorithm. The best-case time complexity is often denoted by the notation O(f(n)), where f(n) is a function representing the minimum number of operations required as a function of the input size n.

Average Time Complexity

Average time complexity refers to the average amount of time an algorithm takes to execute across all possible inputs of a given size. It is an estimation of the expected running time of the algorithm when considering various input distributions. The average-case time complexity is denoted by O(f(n)), where f(n) represents the average number of operations required for input size n.

Worst Time Complexity

This represents the maximum amount of time an algorithm takes to execute for a given input size, considering the most unfavorable scenario. It provides an upper bound on the running time of the algorithm and is denoted by O(f(n)), where f(n) is a function representing the maximum number of operations required as a function of the input size n. The worst-case time complexity is crucial for assessing the algorithm's performance in the most demanding situations.

Sorting Algorithms Time and Space Complexity Cheat Sheet

Algorithm

Time Complexity

Space Complexity

(Worst Case)

Selection Sort

O(N^2)

O(N^2)

O(N^2)

O(1)

Insertion Sort

O(N^2)

O(N^2)

O(N^2)

O(1)

Bubble Sort

O(N^2)

O(N^2)

O(N^2)

O(1)

Merge Sort

O(N log N)

O(N log N)

O(N log N)

O(N)

Quick Sort

O(N log N)

O(N log N)

O(N^2)

O(N)

Heap Sort

O(N log N)

O(N log N)

O(N log N)

O(1)

Counting Sort

O(N + K)

O(N + K)

O(N + K)

O(K)

Radix Sort

O(N * K)

O(N * K)

O(N * K)

O(N + K)

Bucket Sort

O(N + K)

O(N + K)

O(N^2)

O(N)

Count Sort

O(N+K)

O(N+K)

O(N+K)

O(N+K)

Shell Sort

O(1)

O(1) to O(Nlog^{2}N)

O(1) to O(Nlog^{2}N)

O(1)

Tim Sort

O(N)

O(NlogN)

O(NlogN)

O(N)

Tree Sort

O(N)

O(NlogN)

O(N^{2})

O(N)

Cube Sort

O(N)

O(NlogN)

O(NlogN)

O(N)

Selection Sort

Selection Sort is one of the brute force approaches to sort an array. It divides the array into two subarrays: sorted and unsorted. Initially, the sorted subarray is empty, and the original array is the unsorted subarray. Then, it repeatedly finds the least element in the unsorted subarray and puts it at the end of the sorted subarray.

Time Complexity

The algorithm iterates the unsorted subarray (N - 1) times, and, after every iteration, the size of the unsorted subarray reduces by one. Thus the total number of comparisons is (N - 1) + (N - 2) + (N - 3) + ........... + 1 which is N * (N - 1)/2. So, the time complexity is quadratic.

It performs the same number of comparisons for any given array of size N, so the worst, best, and average cases are equal.

Worst Case = Best Case = Average Case O(n^2)

Space Complexity

The algorithm doesn't use any extra space, so the space complexity is constant.

Insertion Sort

Similar to selection sort, Insertion sort also divides the array into two parts: sorted and unsorted. But in insertion sort, the sorted subarray initially contains the first element. Then the algorithm repeatedly picks the elements from the unsorted subarray and puts them at the correct position in the sorted subarray.

Time Complexity

Best Case

If the array is already sorted, then the algorithm picks the first element from the unsorted subarray and puts it at the end of the sorted subarray. So the time complexity for the sorted array is O(n).

Worst Case

For the array sorted in reverse order, the algorithm picks the first element from the unsorted subarray and places it at the beginning of the sorted subarray. Thus the total number of comparisons is N * (N - 1)/2. so the worst-case time complexity is O(N^2).

Average Case

The average case time complexity of insertion sort is also O(N^2).

Space Complexity

The algorithm doesn't use any extra space other than the original array, so the space complexity is O(1).

Bubble Sort

If the array is already sorted, then in the first pass, we do not perform any swap. Then, we know that no more swaps are required. So we can stop sorting. Thus the best time complexity turns out to be linear.

Time complexity

Best Case

If the array is already sorted, then in the first pass, we do not perform any swap. Then, we know that no more swaps are required. So we can stop sorting. Thus the best case time complexity is linear.

Worst Case

If the array is sorted in reverse order, then in the first pass, we perform (N - 1) swaps, (N - 2) in second, (N - 3) in third, and so on. Thus the total number of swaps is N * (N - 1)/2. So, the overall time complexity is O(n * n).

Average Case

The average number of swaps for any random array is (N^2)/4, so the average case time complexity is O(N^2).

Space Complexity

The algorithm doesn't use any extra space other than the original array, so the space complexity is O(1).

Merge Sort

Merge sort is one of the most efficient sorting techniques. It follows divide and conquer strategy. It first divides the original array into N subarrays of size one each and then repeatedly merges two in sorted order.

Time complexity

The merge sort performs the same number of operations regardless of the input array. It divides the array recursively into two subarrays of equal size which will create logN subarrays. Then it repeatedly merges two subarrays in sorted order, which take linear time. So, the overall complexity is O(N log N).

Best case = worst case = average case = O(N logN)

Space complexity

An extra array of size N is needed to store the merged array. Thus the space complexity is O(N).

Quick Sort

Similar to merge sort, quick sort also uses divide and conquer strategy. It selects an element as a pivot and partitions the array around it. It moves all the elements less than pivot to its left and all the elements greater than it to the right, then recursively sorts the subarrays.

Time Complexity

Time complexity of quick sort depends upon the pivot element.

Worse Case

When the array is already sorted, and we select the leftmost elements as a pivot, the algorithm recursively creates N subarrays of size N, N - 1, N - 2,.......,1. As the array is sorted, each subarray requires linear time for partitioning, resulting in quadratic time complexity.

Best Case

If we pick the median element as a pivot every time, then the algorithm creates logN subarrays (similar to merge sort). So for such a case, the time complexity is O(NlogN), which is the best case time complexity.

Average Case

There are many ways to avoid the worst case of quicksort, like choosing the element from the middle of the array as pivot, randomly generating a pivot for each subarray, selecting the median of the first, last, and middle element as pivot, etc. By using these methods, we can ensure equal partitioning, on average. Thus, quick sort's average case time complexity is O(NlogN).

Space Complexity

Unlike merge sort quicksort doesn't require any extra space to store arrays but additional memory is required for creating stack frames in recursive calls. So, the space complexity again depends on the pivot.

Worse Case

If we select the largest or smallest element as a pivot, there are in total N recursive calls, so the size of the recursion tree will be N. Thus, the space complexity for such a case is O(N) which is the worst case.

Best Case

If we manage to partition the array in equal halves each time, then the size of the recursion tree is logN. So, in this case, the space complexity is O(N log N).

Heap Sort

In the heap sort, we convert the given array into min-heap or max-heap. Then we repeatedly fetch the largest or smallest element from the heap and place them accordingly.

Time Complexity

On average, O(logN) time is required to fetch the smallest or largest element from the heap, and we have to fetch N elements. So overall time complexity of quicksort is O(NlogN).

The order of time taken by quicksort is always the same irrespective of the array.

Best case = Worst case = Average case = O(N log N)

Space complexity

Heap sort doesn't require extra space as it simply converts the given array into a heap. Therefore, its space complexity is O(1).

Counting Sort

Counting sort keeps the number of occurrences of each unique element in the given array into an auxiliary array of size K, equal to the range of elements in the input.

K = (max element - minimum element + 1)

Then, this auxiliary array is used to sort the given array.

Time Complexity

The time complexity to iterate over each element in the given input is O(N). Then the algorithm iterates through the auxiliary array that contributes O(K) time complexity. So, the overall time complexity is O(N + K).

Best case = worst case = average case = O(N + K)

The time complexity of the counting sort is linear, but we can't use it if the range of input elements is large.

Space complexity

The algorithm requires an auxiliary array of size K, so the space complexity is O(k).

Radix Sort

Radix sort overcomes the problem of counting sort. It sorts the array digit by digit. It starts with the least significant digit and moves to the next significant digit, and sorts based on that digit. In the case of a tie, it uses the sorted order of the previous digit. It uses the counting sort for a particular digit.

Time Complexity

Let K be the number of digits in the maximum element of the array and b be the base of array elements.

The counting sort for a particular digit takes O(N + b) time, and the algorithm runs the counting sort for all the K digits. Therefore, the total time complexity is O(K * (N + b))

best case = worst case = average case = O(K * (N + b))

Space Complexity

The space complexity of radix sort is the same as counting sort, which is O(N + K).

Bucket Sort

By suitably mapping each element to a bucket, we partition the array into several groups called buckets in bucket sort. The contents from the buckets are then progressively gathered to form the sorted array, which is then sorted using any efficient sorting algorithm. The input characteristic determines the mapping function.

Time Complexity

Worst Case

When all elements in an array are the same, the algorithm puts them all in the same bucket. The overall time complexity will become quadratic if we apply a quadratic time complexity algorithm to sort that bucket, such as insertion sort, selection sort, etc.

Average Case and Best Case

Bucket sort runs in linear time when the elements are spread randomly in the array (e.g., Given array is a permutation of size N), as long as the sum of the squares of the bucket sizes is linear in the total number of items.

Space Complexity

If K is the number of buckets required, then O(K) extra space is needed to store K empty buckets, and then we map each element to a bucket that requires O(N) extra space. So the overall space complexity is O(N + K).

Count Sort

Count Sort is a sorting algorithm that works by counting the occurrences of each unique element and arranging them in sorted order. It is efficient for sorting integers within a specific range.

Time Complexity

Count Sort has a time complexity of O(n+k), where n is the number of elements in the input array and k is the range of the input.

Space Complexity

Count Sort has a space complexity of O(n+k) due to the additional space required for counting the occurrences of elements and storing the sorted output.

Shell Sort

Shell Sort is an in-place comparison-based sorting algorithm that divides the array into smaller subarrays and sorts them independently using an insertion sort. It has better performance than insertion sort on average.

Time Complexity

Shell Sort has a time complexity ranging from O(1) to O(nlog^{2}n) depending on the gap sequence used.

Space Complexity

Shell Sort has a space complexity of O(1) as it operates in-place, requiring only a constant amount of extra space.

Tim Sort

Tim Sort is a hybrid sorting algorithm derived from merge sort and insertion sort. It partitions the array into blocks, sorts them individually using insertion sort, and then merges them together.

Time Complexity

Tim Sort has a time complexity of O(nlogn) on average and worst-case scenarios due to its merge sort-based strategy.

Space Complexity

Tim Sort has a space complexity of O(n) because it requires additional space for merging the sorted blocks.

Tree Sort

Tree Sort is a sorting algorithm that builds a binary search tree from the elements to be sorted and then performs an in-order traversal to retrieve the elements in sorted order.

Time Complexity

Tree Sort has an average time complexity of O(nlogn) and a worst-case time complexity of O(n^{2}) if the tree is unbalanced.

Space Complexity

Tree Sort has a space complexity of O(n) to store the elements in the binary search tree.

Cube Sort

Cube Sort is a variation of merge sort that partitions the array into sub-cubes and sorts them independently, followed by merging the sub-cubes to obtain the sorted array.

Time Complexity

Cube Sort has a time complexity of O(nlogn) on average and in the worst-case scenario due to its merge sort-like strategy.

Space Complexity

Cube Sort has a space complexity of O(n) as it requires additional space for merging the sub-cubes.

Frequently Asked Questions

What is the time complexity of sorting algorithms?

The computational complexity of an algorithm is measured by how long it takes to do a specific action, such as sorting a list of data, and this is known as the time complexity of sorting algorithms.

What is the fastest time complexity for sorting?

The fastest time complexity for sorting is O(nlogn), achieved by algorithms like Merge Sort, Heap Sort, and Tim Sort.

Which sorting algorithm has log n complexity?

Sorting algorithms with log n complexity include Shell Sort, which has a time complexity ranging from O(1) to O(nlog^{2}n).

Which sorting algorithm has a space complexity of O(1)?

Shell Sort typically has a space complexity of O(1) as it operates in-place, requiring only a constant amount of extra space.

Which sorting algorithm has best time complexity?

The quick sort algorithm has the best time complexity of all the sorting algorithms. The best, average, and worst cases of Quicksort's temporal complexity are O(N log N), O(N log N), and O(N log N), respectively.

What is the quick sort time complexity?

The best time complexity of quick sort is O(N log N), and the worst time complexity and the average time complexity of quick sort are also the same as the best, i.e., O(N log N).

Conclusion

In this article, we discussed the space and time complexity of sorting algorithms. Having a good grasp of sorting algorithms is very important to crack coding interviews. You can also check out our other blogs on sorting algorithms to get a better hold on this topic.

To learn more about such Data Structures and algorithms, Coding Ninjas Studio is your one-stop destination. This platform will help you to improve your coding techniques and give you an overview of interview experiences in various product-based companies.

Happy learning!

Live masterclass

Google Data Analyst roadmap: Essential SQL concepts

by Maaheen Jaiswal, Data Analyst @ Google

12 Nov, 2024

01:30 PM

Amazon Data Analyst tips: Advanced Excel interview questions

by Megna Roy, Data Science & Analytics @Amazon

11 Nov, 2024

01:30 PM

Google Data Analyst roadmap: Essential SQL concepts

by Maaheen Jaiswal, Data Analyst @ Google

12 Nov, 2024

01:30 PM

Amazon Data Analyst tips: Advanced Excel interview questions