7. Comparison of Sorting Algorithms

7.1 Performance Summary 
 // Test all sorting algorithms
#include <time.h>

void testSortingAlgorithms() {
 int sizes[] = {100, 1000, 10000};
 
 for (int s = 0; s < 3; s++) {
 int n = sizes[s];
 printf("\n=== Array Size: %d ===\n", n);
 
 // Test each algorithm
 int *arr = generateRandomArray(n);
 
 clock_t start = clock();
 bubbleSort(arr, n);
 clock_t end = clock();
 printf("Bubble Sort: %.4f seconds\n", 
 (double)(end - start) / CLOCKS_PER_SEC);
 
 // Repeat for other algorithms...
 free(arr);
 }
}
 
 7.2 When to Use Which Algorithm 
 Decision Tree: 
 Is n < 50?
├─ Yes → Use Insertion Sort (simple, fast for small n)
└─ No → Is stability required?
 ├─ Yes → Use Merge Sort
 └─ No → Is memory limited?
 ├─ Yes → Use Quick Sort (in-place)
 └─ No → Use Merge Sort (guaranteed O(n log n))
 
 By Data Characteristics: 
 Nearly sorted →Insertion Sort (O(n))
Reverse sorted → Any O(n log n) algorithm
Random data → Quick Sort (fastest in practice)
Many duplicates → Quick Sort 3-way
Small data → Insertion Sort
Large data → Merge Sort or Quick Sort
Linked list → Merge Sort (O(1) space)
Stability needed → Merge Sort or Insertion Sort
Memory limited → Quick Sort or Heap Sort
 
 7.3 Hybrid Sorting Approaches 
 IntroSort (Introspective Sort): 
 void introSort(int arr[], int low, int high, int depthLimit) {
 int n = high - low + 1;
 
 // Use Insertion Sort for small arrays
 if (n < 16) {
 insertionSort(arr + low, n);
 return;
 }
 
 // Switch to Heap Sort if recursion too deep
 if (depthLimit == 0) {
 heapSort(arr + low, n);
 return;
 }
 
 // Use Quick Sort
 int pi = partition(arr, low, high);
 introSort(arr, low, pi - 1, depthLimit - 1);
 introSort(arr, pi + 1, high, depthLimit - 1);
}

// Wrapper function
void sort(int arr[], int n) {
 int depthLimit = 2 * log2(n);
 introSort(arr, 0, n - 1, depthLimit);
}
 
 TimSort (Python's default sort): 
 
 Combination of Merge Sort and Insertion Sort 
 Identifies natural runs in data 
 Uses Insertion Sort for small runs 
 Merges runs using Merge Sort