Time and Space Complexities of Sorting Algorithms Explained

Abhishek Ranjan
Last Updated: May 13, 2022

Introduction

 

Sorting algorithms are very important algorithms in computer science. Having a good grasp of sorting algorithms is necessary to solve complex problems efficiently. 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 time and space complexity of the popular sorting algorithms:  Selection Sort, Insertion Sort, Bubble Sort, Merge Sort, Quicksort, Heap Sort, Counting Sort, Radix Sort, and Bucket Sort. 

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 minimum 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 are (N - 1) + (N - 2) + (N - 3) + ........... + 1 which is N * (N - 1)/2. So, the overall 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 maximum or minimum element from the heap and place them accordingly.

Time Complexity

On average, O(logN) time is required to fetch the minimum or maximum 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 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).

 

Cheat Sheet

 

  Algorithm                    Time Complexity

    Space Complexity

(Worst Case)

Selection SortO(N^2)O(N^2)O(N^2)O(1)
Insertion SortO(N^2)O(N^2)O(N^2)O(1)
Bubble SortO(N^2)O(N^2)O(N^2)O(1)
Merge SortO(N log N)O(N log N)O(N log N)O(N)
Quick SortO(N log N)O(N log N)O(N^2)  O(N)
Heap SortO(N log N)O(N log N)O(N log N)O(1)
Counting SortO(N + K)O(N + K)O(N + K)O(K)
Radix SortO(N * K)O(N * K)O(N * K)O(N + K)
Bucket SortO(N + K)O(N + K)O(N^2)O(N)

 

 

 

 

FAQs

  1. What is time complexity?
    The amount of time an algorithm needs is known as the time complexity of an algorithm. It is represented in terms of the characteristics of the input. It also gives the approximation of the total number of elementary operations executed throughout the program.
     
  2. What is space complexity?
    The approximate total additional space required by an algorithm to run is known as space complexity. Generally represented in terms of input size.

Key Takeaways

In this article, we discussed time and space complexity of sorting algorithms. Having a good grasp of sorting algorithms is very important to crack the coding interviews. Check out this coding ninjas blog on sorting algorithms for getting a better hold on it.

To learn more about such data structures and algorithms, Codestudio is a 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 by providing Online Mock Test Series and many more benefits.

Happy learning!

Was this article helpful ?
2 upvotes