- An in-place algorithm is an algorithm that does not need an extra space and produces an output in the same memory that contains the data by transforming the input ‘in-place’. However, a small constant extra space used for variables is allowed.
- Inplace means O(1)
- Inplace sorting algos : Bubble, Insertion, Selection, Heap
- Stable sorting algos : Bubble,Insertion,Merge,Counting,Bucket
| Algo | Average Case | Best Case | Worst Case | Inplace | Stable |
|---|---|---|---|---|---|
| Bubble Sort | O(N^2) | O(N) | O(N^2) | Yes | Yes |
| Insertion Sort | O(N^2) | O(N) | O(N^2) | Yes | Yes |
| Selection Sort | O(N^2) | O(N^2) | O(N^2) | Yes | No |
| Merge Sort | O(N logN) | O(N logN) | O(N logN) | O(N) | Yes |
| Heap Sort | O(N logN) | O(N logN) | O(N logN) | Yes | No |
| Quick Sort | O(N logN) | O(N logN) | O(N^2) | O(N logN) | No |
| Counting Sort | O(N) | O(N) | O(N^2) | O(N) | Yes |
| Radix Sort | O(N) | O(N) | O(N) | O(N) | No |
| Bucket Sort | O(N) | O(N) | O(N^2) | O(N) | Yes |
- Selection Sort : Find min element in unsorted array and swap it with the element at beginning.
- Bubble Sort : Repeatedly swap two adjacent elements if they are in wrong order.
- Insertion Sort : Insert an element from unsorted array to its correct position in sorted array.
- Wave sort is imp.
- DNF sort means sort an arary of 0s,1s and 2s.
- In quick sort, pivot is the end element(worst case).
- In quick sort, pivot is the median element(best case).