# 7. Comparison of Sorting Algorithms

### 7.1 Performance Summary

```c
// 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):**
```c
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