i1.What is the most efficient way to sort a million integers?
Contents
Q. What is the most efficient way to sort a million integers?
Time Complexity
| Sorting Algorithm | Average Case | Best Case | Worst Case |
|---|---|---|---|
| Bubble Sort | O(n^2) | O(n) | O(n^2) |
| Insertion Sort | O(n^2) | O(n) | O(n^2) |
| Selection Sort | O(n^2) | O(n^2) | O(n^2) |
| Quick Sort | O(n.log(n)) | O(n.log(n)) | O(n^2) |
| Merge Sort | O(n.log(n)) | O(n.log(n)) | O(n.log(n)) |
| Heap Sort | O(n.log(n)) | O(n.log(n)) | O(n.log(n)) |
| Counting Sort | O(n+k) | O(n+k) | O(n+k) |
| Radix Sort | O(n*k) | O(n*k) | O(n*k) |
| Bucket Sort | O(n+k) | O(n+k) | O(n^2) |
Space Complexity
| Sorting Algorithm | Space Complexity |
|---|---|
| Bubble Sort | O(1) |
| Insertion Sort | O(1) |
| Selection Sort | O(1) |
| Quick Sort | O(log(n)) |
| Merge Sort | O(n) |
| Heap Sort | O(1) |
| Counting Sort | O(k) |
| Radix Sort | O(n + k) |
| Bucket Sort | O(n) |
Stability
| Sorting Algorithm | Stable Sort? |
|---|---|
| Bubble Sort | Yes |
| Insertion Sort | Yes |
| Selection Sort | No |
| Quick Sort | No |
| Merge Sort | Yes |
| Heap Sort | No |
| Counting Sort | Yes |
| Radix Sort | Yes |
| Bucket Sort | Yes |
Consider above all, merge sort will be the best choice.