The purpose of sorting is to systematically rearrange elements within a list, establishing an ascending or descending order. There are two types of sorting techniques.
1. Internal Sorting:
- The sorting deals with the list of elements stored in the computer memory. The different types of internal sorting are
2. External Sorting:
- This sorting is used when there is a large data that cannot be stored in memory. The data is stored in Files.
Complexity Analysis of Sorting Techniques
| Sorting Technique | Time Complexity | Auxiliary Space Complexity | Space Complexity |
| Bubble Sort | O(n^2) | O(1) | O(1) |
| Selection Sort | O(n^2) | O(1) | O(1) |
| Insertion Sort | O(n^2) | O(1) | O(1) |
| Merge Sort | O(n log n) | O(n) | O(n) |
| Quick Sort | O(n log n) | O(log n) | O(log n) |
| Heap Sort | O(n log n) | O(1) | O(1) |
| Counting Sort | O(n + k) | O(k) | O(k) |
| Radix Sort | O(nk) | O(k) | O(k) |
Time Complexity:
- Bubble Sort, Selection Sort, Insertion Sort: O(n^2) – These algorithms compare each element with its neighbors, leading to quadratic time complexity.
- Merge Sort, Quick Sort, and Heap Sort boast an average-case time complexity of O(n log n) due to their shared strategy of recursively partitioning the array into smaller, more manageable subarrays and then merging them back together in a sorted fashion. This divide-and-conquer approach results in logarithmic time complexity.
- Counting Sort, Radix Sort: O(nk) – These algorithms exploit the knowledge of the range of values in the input array to sort elements in a linear fashion based on their counts or digits.
Auxiliary Space Complexity:
- Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Heap Sort: O(1) – These algorithms use only a small additional space for temporary variables, pointers, or recursion stack.
- Quick Sort: O(log n) – In the worst case, Quick Sort can use up to log n space for the recursion stack.
- Counting Sort, Radix Sort: O(k) – These algorithms require additional space for arrays or structures to store counts or digits.
Space Complexity:
- Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, Heap Sort: O(1) – These algorithms only modify the input array in place, resulting in constant space complexity.
- Quick Sort: O(log n) – In the worst case, Quick Sort can use up to log n space for the recursion stack.
- Counting Sort, Radix Sort: O(k) – These algorithms require additional space for arrays or structures to store counts or digits.