Sorting Algorithm

In this article, you will learn what sorting algorithm is and different sorting algorithms.

A sorting algorithm is used to arrange elements of an array/list in a specific order. For example,

Sorting an array
Sorting an array

Here, we are sorting the array in ascending order.

There are various sorting algorithms that can be used to complete this operation. And, we can use any algorithm based on the requirement.

1. Different Sorting Algorithms

2. Complexity of Sorting Algorithms

The efficiency of any sorting algorithm is determined by the time complexity and space complexity of the algorithm.

1. Time Complexity: Time complexity refers to the time taken by an algorithm to complete its execution with respect to the size of the input. It can be represented in different forms:

2. Space Complexity: Space complexity refers to the total amount of memory used by the algorithm for a complete execution. It includes both the auxiliary memory and the input.

The auxiliary memory is the additional space occupied by the algorithm apart from the input data. Usually, auxiliary memory is considered for calculating the space complexity of an algorithm.

Let’s see a complexity analysis of different sorting algorithms.

Sorting AlgorithmTime Complexity – BestTime Complexity – WorstTime Complexity – AverageSpace Complexity
Bubble Sortnn2n21
Selection Sortn2n2n21
Insertion Sortnn2n21
Merge Sortnlog nnlog nnlog nn
Quicksortnlog nn2nlog nlog n
Counting Sortn+kn+kn+kmax
Radix Sortn+kn+kn+kmax
Bucket Sortn+kn2nn+k
Heap Sortnlog nnlog nnlog n1
Shell Sortnlog nn2nlog n1

3. Stability of Sorting Algorithm

A sorting algorithm is considered stable if the two or more items with the same value maintain the same relative positions even after sorting.

For example, in the image below, there are two items with the same value 3. An unstable sorting algorithm allows two possibilities where the two positions of 3 may or may not be maintained.

Unstable Sorting
Unstable sorting with two possible outcomes

However, after a stable sorting algorithm, there is always one possibility where the positions are maintained as in the original array.

Stable sorting
Stable sorting with the positions preserved

Here’s a table showing the stablilty of different sorting algorithm.

Sorting AlgorithmStability
Bubble SortYes
Selection SortNo
Insertion SortYes
Merge SortYes
Counting SortYes
Radix SortYes
Bucket SortYes
Heap SortNo
Shell SortNo