Time Complexities of all Sorting Algorithms

Last Updated : 22 Feb, 2024

The efficiency of an algorithm depends on two parameters:

Time Complexity
Space Complexity

Time Complexity:

Time Complexity is defined as the number of times a particular instruction set is executed rather than the total time taken. It is because the total time taken also depends on some external factors like the compiler used, the processor’s speed, etc.

Space Complexity:

Space Complexity is the total memory space required by the program for its execution.

Both are calculated as the function of input size(n). One important thing here is that despite these parameters, the efficiency of an algorithm also depends upon the nature and size of the input.

Types of Time Complexity :

Best Time Complexity: Define the input for which the algorithm takes less time or minimum time. In the best case calculate the lower bound of an algorithm. Example: In the linear search when search data is present at the first location of large data then the best case occurs.
Average Time Complexity: In the average case take all random inputs and calculate the computation time for all inputs.
And then we divide it by the total number of inputs.
Worst Time Complexity: Define the input for which algorithm takes a long time or maximum time. In the worst calculate the upper bound of an algorithm. Example: In the linear search when search data is present at the last location of large data then the worst case occurs.

Following is a quick revision sheet that you may refer to at the last minute:

Algorithm	Time Complexity			Space Complexity
	Best	Average	Worst	Worst
Selection Sort	O(n²)	O(n²)	O(n²)	O(1)
Bubble Sort	O(n)	O(n²)	O(n²)	O(1)
Insertion Sort	O(n)	O(n²)	O(n²)	O(1)
Heap Sort	O(n log(n))	O(n log(n))	O(n log(n))	O(1)
Quick Sort	O(n log(n))	O(n log(n))	O(n²)	O(n)
Merge Sort	O(n log(n))	O(n log(n))	O(n log(n))	O(n)
Bucket Sort	O(n +k)	O(n +k)	O(n²)	O(n)
Radix Sort	O(nk)	O(nk)	O(nk)	O(n + k)
Count Sort	O(n +k)	O(n +k)	O(n +k)	O(k)
Shell Sort	O(n log(n))	O(n log(n))	O(n²)	O(1)
Tim Sort	O(n)	O(n log(n))	O(n log (n))	O(n)
Tree Sort	O(n log(n))	O(n log(n))	O(n²)	O(n)
Cube Sort	O(n)	O(n log(n))	O(n log(n))	O(n)

Also, see:

Time and Space complexity of Radix Sort Algorithm

kartik

News

Improve

Similar Reads

Time Complexities of all Sorting Algorithms

The efficiency of an algorithm depends on two parameters: Time ComplexitySpace ComplexityTime Complexity:Time Complexity is defined as the number of times a particular instruction set is executed rather than the total time taken. It is because the total time taken also depends on some external facto

Time and Space complexity of Radix Sort Algorithm

The Radix Sort Algorithm has a time complexity of O(n*d), where n is the number of elements in the input array and d is the number of digits in the largest number. The space complexity of Radix Sort is O(n + k), where n is the number of elements in the input array and k is the range of the input. Th

The Slowest Sorting Algorithms

A Sorting Algorithm is used to rearrange a given array or list elements according to a comparison operator on the elements. The comparison operator is used to decide the new order of the element in the respective data structure. But Below is some of the slowest sorting algorithms: Stooge Sort: A Sto

Classification of Sorting Algorithms

Sorting is an algorithm which arranges the elements of a given list in a particular order [ascending or descending]. Sorting algorithms are categorized on the following basis - By number of comparisons :Comparison-based sorting algorithms check the elements of the list by key comparison operation an

Time and Space Complexity Analysis of Merge Sort

The Time Complexity of Merge Sort is O(n log n) in both the average and worst cases. The space complexity of Merge sort is O(n). AspectComplexityTime ComplexityO(n log n)Space ComplexityO(n)Time Complexity Analysis of Merge Sort:Consider the following terminologies: T(k) = time taken to sort k eleme

Time and Space Complexity Analysis of Bubble Sort

The time complexity of Bubble Sort is O(n^2) in the worst-case scenario and the space complexity of Bubble sort is O(1). Bubble Sort only needs a constant amount of additional space during the sorting process. Complexity TypeComplexityTime ComplexityBest: O(n)Average: O(n^2)Worst: O(n^2)Space Comple

Time and Space Complexity Analysis of Quick Sort

The time complexity of Quick Sort is O(n log n) on average case, but can become O(n^2) in the worst-case. The space complexity of Quick Sort in the best case is O(log n), while in the worst-case scenario, it becomes O(n) due to unbalanced partitioning causing a skewed recursion tree that requires a

Asymptotic Analysis and comparison of sorting algorithms

It is a well established fact that merge sort runs faster than insertion sort. Using asymptotic analysis. we can prove that merge sort runs in O(nlogn) time and insertion sort takes O(n^2). It is obvious because merge sort uses a divide-and-conquer approach by recursively solving the problems where

Can Run Time Complexity of a comparison-based sorting algorithm be less than N logN?

Sorting algorithms are the means to sort a given set of data in an order according to the requirement of the user. They are primarily used to sort data in an increasing or decreasing manner. There are two types of sorting algorithms: Comparison-based sorting algorithmsNon-comparison-based sorting al

When to use each Sorting Algorithms | Set 2

Sorting is the process of arranging a set of data in a specific order, which may be numerical (ascending, descending) or lexicographical (alphabetical) order. Why Sorting Is Required? Sorting is very essential when there is a need to highly optimize the searching algorithm. For example, let's assume

Lower bound for comparison based sorting algorithms

The problem of sorting can be viewed as following. Input: A sequence of n numbers <a1, a2, . . . , an>. Output: A permutation (reordering) <a'1, a'2, . . . , a'n> of the input sequence such that a'1 <= a'2 ..... <= a'n. A sorting algorithm is comparison based if it uses comparison

Time and Space complexity analysis of Selection Sort

The Selection sort algorithm has a time complexity of O(n^2) and a space complexity of O(1) since it does not require any additional memory space apart from a temporary variable used for swapping. Time Complexity Analysis of Selection Sort:Best-case: O(n2), best case occurs when the array is already

When to use each Sorting Algorithm

A sorting algorithm is an algorithm that makes the input data set arranged in a certain order. The fundamental task is to put the items in the desired order so that the records are re-arranged for making searching easier. Below is one by one description of when to use which sorting algorithm for bet

Sorting by combining Insertion Sort and Merge Sort algorithms

Insertion sort: The array is virtually split into a sorted and an unsorted part. Values from the unsorted part are picked and placed at the correct position in the sorted part.Advantages: Following are the advantages of insertion sort: If the size of the list to be sorted is small, insertion sort ru

Which sorting algorithm makes minimum number of memory writes?

Minimizing the number of writes is useful when making writes to some huge data set is very expensive, such as with EEPROMs or Flash memory, where each write reduces the lifespan of the memory. Among the sorting algorithms that we generally study in our data structure and algorithm courses, Selectio

Sorting Algorithms

A Sorting Algorithm is used to rearrange a given array or list of elements in an order. Sorting is provided in library implementation of most of the programming languages. Basics of Sorting Algorithms:Introduction to Sorting Applications of Sorting Sorting Algorithms:Comparison Based : Selection Sor

Hybrid Sorting Algorithms

Hybrid sorting algorithms combine two or more standard sorting techniques to optimize performance. For example, Insertion sort works well for small inputs and Quick Sort for large and IntroSort (A Hybrid Sorting Algorithm) uses these properties for using Quick Sort while the input is large and switc

Improvement on the Quick Sort Algorithm

Prerequisite: QuickSort Algorithm The quicksort algorithm discussed in this article can take O(N2) time in the worst case. Hence, certain variations are needed which can efficiently partition the array and rearrange the elements around the pivot. Single Pivot Partitioning: In single pivot partitioni

Sorting objects using In-Place sorting algorithm

Given an array of red, blue and yellow objects, the task is to use an in-place sorting algorithm to sort the array in such a way that all the blue objects appear before all the red objects and all the red objects appear before all the yellow objects.Examples: Input: arr[] = {"blue", "red", "yellow",

Article Tags :

Practice Tags :

Sorting

翻译：