Sorting Algorithms

There are a lot of different sorting algorithms, each having its own benefits. Thus, it is important to know the advantages and disadvantages of algorithms to use them efficiently. Below is the metrics of some of the most popular sorting techniques to help us make better decisions while choosing an algorithm.

Bubble Sort

Bubble sort is one of the easiest algorithms to implement. It basically focuses on placing the largest element of the unsorted sublist at its correct position after each iteration. Bubble sort works well for small datasets but is not generally preferred due to its high time complexity.

Time complexity (best) : O(n)
Time complexity (avg) : O(n^2)
Time complexity (worst) : O(n^2)
Space complexity : O(1)
Stable : Yes
Comparison based : Yes

Click here to know more about bubble sort!

Selection Sort

Selection sort finds the smallest element of the unsorted sublist and swaps it with the leftmost unsorted element. The advantage of selection sort is that it requires the least number of swaps compared to any other sorting algorithm.

Time complexity (best) : O(n^2)
Time complexity (avg) : O(n^2)
Time complexity (worst) : O(n^2)
Space complexity : O(1)
Stable : No
Comparison based : Yes

Click here to know more about selection sort!

Merge Sort

Merge sort is one of the most commonly used and efficient algorithm. It uses divide and conquer approach. Merge sort also works faster than quick sort in case of very large datasets.

Time complexity (best) : O(n log(n))
Time complexity (avg) : O(n log(n))
Time complexity (worst) : O(n log(n))
Space complexity : O(n)
Stable : Yes
Comparison based : Yes

Click here to know more about merge sort!

Quick Sort

Quick sort is one of the most efficient sorting algorithms also using divide and conquer approach. Unlike merge sort, it is in-place and is also faster than merge sort in case of smaller datasets. Unlike other algorithms, the worst case of quicksort occurs when the array is either sorted in ascending/descending order, or if all elements of the arrays are exactly the same.

Time complexity (best) : O(n log(n))
Time complexity (avg) : O(n log(n))
Time complexity (worst) : O(n^2)
Space complexity : O(n log(n))
Stable : No
Comparison based : Yes

Click here to know more about quick sort!

Counting Sort

Counting sort sorts an array by counting the frequency of occurrences of unique elements. It is not a general purpose sorting algorithm and is used when the elements in an array are in a range from 1 to k.

Time complexity (best) : O(n+k)
Time complexity (avg) : O(n+k)
Time complexity (worst) : O(n+k)
Space complexity : O(k)
Stable : Yes
Comparison based : No

Click here to know more about counting sort!