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,

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

• Bubble Sort
• Selection Sort
• Insertion Sort
• Merge Sort
• Quicksort
• Counting Sort
• Radix Sort
• Bucket Sort
• Heap Sort
• Shell Sort

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:

• Big-O notation (O)
• Omega notation (Ω)
• Theta notation (Θ)

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 Algorithm	Time Complexity – Best	Time Complexity – Worst	Time Complexity – Average	Space Complexity
Bubble Sort	n	n2	n2	1
Selection Sort	n2	n2	n2	1
Insertion Sort	n	n2	n2	1
Merge Sort	nlog n	nlog n	nlog n	n
Quicksort	nlog n	n2	nlog n	log n
Counting Sort	n+k	n+k	n+k	max
Radix Sort	n+k	n+k	n+k	max
Bucket Sort	n+k	n2	n	n+k
Heap Sort	nlog n	nlog n	nlog n	1
Shell Sort	nlog n	n2	nlog n	1

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.

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

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

Sorting Algorithm	Stability
Bubble Sort	Yes
Selection Sort	No
Insertion Sort	Yes
Merge Sort	Yes
Quicksort	No
Counting Sort	Yes
Radix Sort	Yes
Bucket Sort	Yes
Heap Sort	No
Shell Sort	No