We know that ,one problem can be solved by different different way, But main purpose of Algorithm to choose best one for specific problems.
There are following points should be focus :
- Problem types.
- Types of Input Data.
- Structure of Input Data. etc
Example :
- When Array is Unsorted then merge sort is best choice because in all cases time complexity will be O(nlogn).
In the case of Unsorted array, we can also use another sorting algorithm like Quick Sort,Bubble Sort etc… but In this situation Merge sort is best choice.
- When array or list are Sorted(almost, not complete), then insertion Sort is good choice.because Insertion gives best performance in the form of time and space.
- When array or list are completely Sorted ,then we can choose Insertion sort or selection sort.because it will give O(n) time complexity.
Comparison Table
| Sorting Algorithm | Worst Case | Best Case | Average Case | Auxiliary Memory | Is Stable? |
|---|---|---|---|---|---|
| Bubble Sort | O(n^{2}) | O(n) | O(n^{2}) | O(1) | Yes |
| Selection Sort | O(n^{2}) | O(n^{2}) | O(n^{2}) | O(1) | No |
| Insertion Sort | O(n^{2}) | O(n) | O(n^{2}) | O(1) | Yes |
| Merge Sort | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | Yes |
| Quick Sort | O(n^{2}) | O(nlogn) | O(nlogn) | O(logn) | No |
| Heap Sort | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | No |