 # Sorting Algorithm

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.

## 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 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

## 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