What is Sorting?


A Sorting Algorithm is used to reorder elements in an array or list based on a comparison operator on the elements. The comparison operator determines the new order of items in a data structure.


Important Sorting Algorithms:


  1. Bubble Sort
  2. Selection Sort
  3. Insertion Sort
  4. Merge Sort
  5. Quick Sort
  6. Counting Sort
  7. Radix Sort
  8. Heap Sort

Time-Complexities Sorting Algorithms


Bubble Sort:
Best Case: O(n) (when the array is already sorted)
Worst Case: O(n^2)

Selection Sort:
Best Case: O(n^2)
Worst Case: O(n^2)

Insertion Sort:
Best Case: O(n) (when the array is nearly sorted)
Worst Case: O(n^2)

In insertion sort, there is a single pass , but there are many steps. 
 The number of steps utmost in Insertion sort is: 

 1+2+3......................+n , 
where n is number of elements in the list.

 =((n-1)n)/2 =O (n*n)   (TIME COMPLEXITY)

Merge Sort:
Best Case: O(n log n)
Worst Case: O(n log n)

TIME COMPLEXITY: 

 There are total log2 n passes in merge sort and in each pass there are n comparisons atmost. 

 Therefore total number of comparisons=O (n * log2 n). 

In 3 way merge sorting time complexity is O (n log3 n)

Quick Sort:
Best Case: O(n log n)
Worst Case: O(n^2) (rare, can be improved with optimizations)

Heap Sort:
Best Case: O(n log n)
Worst Case: O(n log n)

Counting Sort:
Best Case: O(n + k) (where k is the range of input)
Worst Case: O(n + k)

Radix Sort:
Best Case: O(nk) (where k is the number of digits in the largest number)
Worst Case: O(nk)

Bucket Sort:
Best Case: O(n + k) (when input is uniformly distributed)
Worst Case: O(n^2) (when all elements are placed in a single bucket)