Sorting is the fundamental algorithm in computer science to arrange(ascending or descending) the data elements in the list. It is also one of the most common algorithms that computers performed on data. In this tutorial, we will try to explain some basic as well as advanced sorting algorithms. We will start with the native sorting algorithms and then explore efficient sorting algorithms with their time and space complexity.
Contents [hide]
Why Sorting Algorithms are necessary?
There are lots of advantages if you keep your data in the sorted form in the database.

For faster searching of elements in the database.

Remove the code complexity for data retrieval.
Types Of Sorting Algorithms
There are mainly two types of sorting algorithms.

Comparisonbased sorting algorithms: In this type of sorting algorithm, we need to compare the elements in order to sort the elements.

Linear sorting algorithms: In this type of algorithm, we use some techniques other than comparing the elements to sort the list.
Comparisonbased Sorting Algorithms
1. Bubble Sort
Bubble sort is one of the simplest algorithms for sorting the array in ascending or descending form. It iterates the array elements from 1st element to last and swaps every consecutive pair of elements if they are not in the correct order.
Algorithm

Repeat Step 2 For i = 0 to N1

Repeat For J = i + 1 to N – I

IF A[J] > A[i]
SWAP A[J] and A[i]
[END OF INNER LOOP]
[END OF OUTER LOOP 
EXIT
Complexity
Worst Case Time complexity: O(N2)
Worst Case Space complexity: O(1)
JavaScript Code Implementation
2. Selection Sort
This algorithm repeatedlyfinds the smallest element in the unordered list and places it in the appropriate position.
Algorithm

Repeat Step 2 and 3 For i = 0 to N1

Select the smallest element(MinIndex)

Repeat For J = i + 1 to N – I

IF A[J]< A[MinIndex]
SWAP A[J] and A[MinIndex]
[END OF INNER LOOP]
[END OF OUTER LOOP 
EXIT
Complexity
Worst Case Time complexity: O(N2)
Worst Case Space complexity: O(1)
JavaScript Code Implementation
3. Insertion Sort
Insertion sort selects an element and places it in the correct position. In this sort, we first choose the key element usually 0th element(keyIndex) and compare it with all elements from keyIndex to 0.
Algorithm

Repeat steps 2 and 3 For i = 0 to N1

Select key index starting from 0.

Repeat For J = i – 1 to i

IF A[J] > A[key]
SWAP A[J] and A[key]
key = i
[END OF INNER LOOP]
[END OF OUTER LOOP 
EXIT
JavaScript Code Implementation
Complexity
Worst Case Time complexity: O(N2)
Worst Case Space complexity: O(1)
4. Shell Sort
Shell sort is thegeneralization of insertion sort. In the insertion sort, consecutive elements are compared to get the sorted list but in the shell sort, wecomparing elements separated by a gap of several positions. The gap between the elements gradually decreases based on the sequence that we are using.
Shellsort’s key concept is that it compares distant elements first rather than adjacent elements unlike insertion sort.
Some optimal sequences for Sheel Sort

Shell’s original sequence:
N/2, N/4, ... 1

Sedgewick’s increments:
1, 8, 23, 77, 281, 1073, 4193, 16577...4j+1+ 3·2j+ 1

Knuth’s increments:
1, 4, 13, …, (3^{k}– 1) / 2
JavaScript Code
Complexity
Worst Case Time complexity: O(N2)
Worst Case Space complexity: O(1)
5. Quicksort
Suppose there are lots of students in a class and the teacher wants to arrange them according to their height. So there are 2 methods to arrange them in increasing order of height.

The teacher arranges them one by one.

The teacher asks students to arrange themself.
The second way is more efficient and faster which is the idea behind the Quicksort algorithm.
Quicksort is based on a divide and conquer algorithm where an array is divided on the basis of pivot element such that all the elements less than pivot element are on the left side and all the elements greater than pivot element are on the right side.
Algorithm

First, we have to choose a pivot element(Usually the first element is used).

Split the array into two part – the left part which contains all the elements which are less than pivot element and the right part which contains all the elements greater than the pivot. Or we can say that place the pivot element at the correct position and return it.

Recursively repeat the algorithm for both the halves.
JavaScript Code
Complexity
Worst Case Time complexity: O(N2)
Worst Case Space complexity: O(1)
6. Merge sort
Merge sort is another perfect example of a divide and conquer algorithm where we split the array into a singleelement array and merge them using twoway merging method to find the ordered list.
Algorithm

Divide the array list into the smaller lists until we got the single element in the array. Let us say the last divided array into two subarrays called left array and right array.

Compare each element of the left array to the right array and prepare a third array which having the sorted elements.

Repeat until all the subarray is merged into one array.
Complexity
Worst Case Time complexity: O(N*Log(N))
Worst Case Space complexity: O(N)
JavaScript Code
Linear Sorting Algorithms
1. Counting sort
The counting sort algorithm is a linear sorting algorithm that works by counting the occurrence of unique elements in the array.
Algorithm

Find the minimum and maximum elements in the array.

Create a countArray that stores the count of each element.

Iterate over the countArray and find the nonnegative integers. Push the index of a nonnegative integer into the resultarray and decrease the value by 1 until it becomes 0.
Complexity
Worst Case Time complexity: O(N + K)
Worst Case Space complexity: O(K)
JavaScript Code
2. Bucket sort
Bucket sort is a linear sorting algorithm that first divides the elements into groups called buckets. Then each bucket elements are sorted using any sorting algorithm.
Algorithm

Find the maximum number in the given array and how many digits in this maximum number.

Create a 2D array(Buckets) index from 0 to 10.

Insert elements into the buckets according to the range of the bucket. As we find how many digits are present in the maximum number. Suppose there are 2 digits are there. So we need to insert the elements into the bucket on the basis of Ten’s place of the number.

Sort Each bucket element internally and remove them to make the array sorted.
Complexity
Worst Case Time complexity: O(N2)
Worst Case Space complexity: O(n + k)
JavaScript Code
3. Radix sort
Bucket sort is a linear sorting algorithm that first divides the elements into groups called buckets. Then each bucket elements are sorted using any sorting algorithm.
Algorithm

Find the maximum number in the given array and how many digits in this maximum number.

Create a 2D array(Buckets) index from 0 to 10.

From 0 to Number of digits in maximum number.Suppose there are 2 digits in the maximum number then there will be 2 passes in the radix sort

Insert the elements into the bucket on the basis of Ten’s place of the numbers. Remove all the elements and form a new array.

Insert the elements into the bucket on the basis of One’s place of the numbers.

Complexity
Worst Case Time complexity: O(nd) > d is a number of passes.
Worst Case Space complexity: O(N)
JavaScript Code
Time complexity Comparison Of Different Sorting Algorithms
Algorithm 
Average case complexity 
Worstcase complexity 

Bubble Sort  O(N2)  O(N2) 
Selection Sort  O(N2)  O(N2) 
Insertion Sort  O(N2)  O(N2) 
Shell Sort  O(n*log n)  O(N2) 
Quicksort  O(n*log n)  O(N2) 
Merge Sort  O(n*log n)  O(n*log n) 
Counting Sort  O(n + k)  O(n2) 
Bucket Sort  O(n2)  O(n+k) 
Radix Sort  O(dn)  O(dn) 
Find the complete source code on Github
Happy Sorting!
Next Article: Introduction To Searching Algorithms  Linear Search  Binary Search