**********************************************************************************************
1. Bubble Sort:
Time Complexity : Best => O(n) , Worst & Average => O(n*n)
Space Complexity: O(1)
Stablitiy : Stable
Is-In-Place : In-Place
When to use : 1. If array is of small size
2. If array is of large size but nearly sorted
Remark : Easiest to implement
**********************************************************************************************
2. Selection Sort:
Time Complexity : Best & Worst & Average => O(n*n)
Space Complexity: O(1)
Stablitiy : Not-Stable
Is-In-Place : In-Place
When to use : 1. If array is of small size
2. To minimise the number of swaps
Remarks : Bubble sort has more number of swaps as compare to selection
Sort but bubble sort has better best time complexity.
It can also be implemented as stabaly.
Selection sort makes O(n) swaps which is minimum among all sorting algorithms mentioned above.
**********************************************************************************************
3. Insertion Sort:
Time Complexity : Best => O(n) , Worst & Average => O(n*n)
Space Complexity: O(1)
Stablitiy : Stable
Is-In-Place : In-Place
When to use : 1. If array is of small size and nearly sorted
Remark : Standard Libraray of C uses this algo when n becomes smaller
than a threshold and for small size it is better than merge
and quick sort becasue of low constant values and non
recusive in nature.
**********************************************************************************************
4. Heap Sort:
Time Complexity : Best & Worst & Average => O(nLog(n))
Space Complexity: O(1)
Stablitiy : Not-Stable
Is-In-Place : In-Place
When to use : When the input array is large and stable sort is not
required.
Remark : It always guaranteed to be O(nLog(n)) with constant space
which solves the problem of overflow of address space of a
process which may occur in merge and quick sort(recursive stack).
**********************************************************************************************
5. Counting Sort:
Time Complexity : Best & Worst & Average => O(n+k)
Space Complexity: O(n+k)
Stablitiy : Not-Stable
Is-In-Place : In-Place
**********************************************************************************************
6. Merge Sort:
Time Complexity : Best & Worst & Average => O(nLog(n))
Space Complexity: O(n)
Stablitiy : Stable
Is-In-Place : Not-In-Place
Tag : Divide & Conquer
When to use : 1.When we don't have random access(linked list)
[R.A like as we have in array]
2.When array is not to large.
**********************************************************************************************
7. Quick Sort:
Time Complexity : Best => O(nLog(n)) , Worst => O(n*n)
Space Complexity: O(n)
Stablitiy : Not-Stable
Is-In-Place : In-Place
Tag : Divide & Conquer
When to use : 1.It is prefered over merge sort for extremely large array
2.When you don't care about worst case complexity
----------------------------------------------------------------------------------------------
**********************************************************************************************
Quick Sort * Merge Sort
1.Time O(nLog(n)),O(n*n). * O(nLog(n))
2.Space O(1). * O(n)
3.Advantage When random access is there. * When random access is costly(i.e Linked List)
4.Stability Not Stable. * Stable
5.In-Place In-Place. * Not-In-Place
6.Address Never Rise. * May arise when array/list is extremely large
Space
Overflow
Condition
**********************************************************************************************
Merge Sort
Quick Sort