Introduction
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.
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).
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) |
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.
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.
Recommended Articles -
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!
