In this article, we will discuss the time complexity of some of the most popular sorting algorithms.

## The Most Popular Sorting Algorithms

The algorithms that we will be discussing today are listed below

**Bubble Sort****Selection Sort****Insertion Sort****Merge Sort****Quick Sort****Heap Sort**

Please note that ** N** denotes the total number of elements present in the vector.

## Time Complexity Of Popular Sorting Algorithms

Sorting Algorithm | Best Case | Average Case | Worst Case |

Bubble Sort | O(N) | O(N^{2}) | O(N^{2}) |

Selection Sort | O(N^{2}) | O(N^{2}) | O(N^{2}) |

Insertion Sort | O(N) | O(N^{2}) | O(N^{2}) |

Merge Sort | O(Nlog_{2}N) | O(Nlog_{2}N) | O(Nlog_{2}N) |

Quick Sort | O(Nlog_{2}N) | O(Nlog_{2}N) | O(N^{2}) |

Heap Sort | O(Nlog_{2}N) | O(Nlog_{2}N) | O(Nlog_{2}N) |

Let’s expand on the time complexity of the most popular sorting algorithms in this list one, by one.

### Naive Sorting Algorithms

**1. Bubble Sort :** This sorting technique involves the comparison of two adjacent elements of the vector. If we are sorting in ascending order then the one which turns out to be greater among the two is pushed towards the right and the smaller element is pushed towards the left.

Bubble sorting involves the usage of two nested *for* loops, each making nearly N iterations. Hence the overall time complexity of bubble sort is quadratic with N

**2. Selection Sort :** In this method of sorting we select one element from the vector at a time, compare it with all the other elements, and decide the correct position of this particular element in the vector.

It takes N iterations for finding the correct position for one element, and for the total N elements. Effectively it requires **O(NxN)** iterations. Hence this sorting technique is also quadratic in nature

**3. Insertion Sort:** It is very similar to sorting cards. Divide the vector into two parts, one sorted and the other one unsorted. Now, we insert cards(elements) from the unsorted part into the sorted part at their correct position. This method is also quadratic with N.

### More Efficient Sorting Algorithms

**4. Merge Sort:** Alright, so this is also a very popular

*Divide and Conquer*algorithm. In this method, the vector is divided into two smaller sub vectors and these vectors are further divided into smaller subparts until the subparts contain less than or equal to two elements. This is the base case, and we sort these smallest instances of the vectors. The last part involves merging these smaller sorted subarrays.

Merge sort is *linear* in nature for each subarray and in total we have *log2N* smaller instances.

**5. Quick Sort:** In the quick sort method, an element from the vector is selected. We call this selected element

*Pivot*. We shift all the remaining elements smaller than pivot to its left. Shift all the elements greater than the pivot to its right. Repeating this procedure sorts the vector very efficiently.

**6. Heap Sort:** We generate a heap using the elements of the vector. This heap can either be a max or a min-heap. The generation of heap takes

*log*time. We then extract the topmost element from the heap and this also takes log

_{2}N_{2}N iterations. Effectively, extracting N elements would take Nlog

_{2}N iterations.

## Conclusion

In this article, we discussed the time complexities of the most popular sorting algorithms used to sort data structures. Initially, we considered some naive sorting algorithms. But, later we also discussed the time complexity of some of the most efficient sorting algorithms. Please note that, among all the sorting algorithms that we discussed, quicksort is the fastest(Most Efficient). And, Hoarse-Quicksort is the fastest among all the sorting algorithms, it is the algorithm used by the sort function provided by STL(Standard Template Library).

## References

To learn more about sorting algorithms and their time complexity, you can refer to the following sites: