Module 7: Searching & Sorting
By the end of this module, students will be able to:
Understand fundamental searching algorithms and their applicationsImplement linear and binary search algorithmsUnderstand various sorting algorithms and their characteristicsAnalyze time and space complexity of searching and sorting algorithmsCompare different algorithms and choose appropriate ones for specific problemsImplement sorting algorithms in COptimize searching and sorting operationsApply searching and sorting to solve real-world problems

1. Introduction to Searching
1.1 What is Searching? 
 Searching is the process of finding a particular element or checking if an element exists in a data structure (array, linked list, tree, etc.). 
 Real-World Analogies: 
 
 Finding a book in a library 
 Searching for a contact in your phone 
 Looking up a word in a dictionary 
 Finding a file on your computer 
 
 Types of Searching: 
 
 Linear Search - Sequential search through elements 
 Binary Search - Divide and conquer approach (requires sorted data) 
 Jump Search - Jumping ahead by fixed steps 
 Interpolation Search - Improved binary search for uniformly distributed data 
 Exponential Search - Finding range then binary search 
 
 Note: There's actually a lot more searching algorithms, but we'll focus on the most common ones. 
 1.2 Why Study Searching Algorithms? 
 Importance: 
 
 One of the most common operations in programming 
 Critical for database queries 
 Essential for data retrieval systems 
 Foundation for more complex algorithms 
 Performance impact on large datasets 
 
 Performance Metrics: 
 
 Best Case: Minimum number of comparisons 
 Average Case: Expected number of comparisons 
 Worst Case: Maximum number of comparisons 
 Space Complexity: Extra memory required

2. Linear Search
2.1 Concept 
 Linear Search (also called Sequential Search) checks every element in the array sequentially until the target is found or the end is reached. 
 How it works: 
 
 Start from the first element 
 Compare each element with the target 
 If match found, return the position 
 If end reached without match, return -1 
 
 Visual Representation: 
 Array: [10, 25, 30, 15, 40, 35]
Target: 15

Step 1: Check 10 ≠ 15
Step 2: Check 25 ≠ 15
Step 3: Check 30 ≠ 15
Step 4: Check 15 = 15 ✓ Found at index 3!
 
 2.2 Implementation 
 Basic Linear Search 
 #include <stdio.h>

int linearSearch(int arr[], int n, int target) {
 for (int i = 0; i < n; i++) {
 if (arr[i] == target) {
 return i; // Return index if found
 }
 }
 return -1; // Return -1 if not found
}

int main() {
 int arr[] = {10, 25, 30, 15, 40, 35};
 int n = sizeof(arr) / sizeof(arr[0]);
 int target = 15;
 
 int result = linearSearch(arr, n, target);
 
 if (result != -1) {
 printf("Element %d found at index %d\n", target, result);
 } else {
 printf("Element %d not found\n", target);
 }
 
 return 0;
}
 
 Linear Search with Count 
 int linearSearchCount(int arr[], int n, int target, int *comparisons) {
 *comparisons = 0;
 
 for (int i = 0; i < n; i++) {
 (*comparisons)++;
 if (arr[i] == target) {
 return i;
 }
 }
 return -1;
}

// Usage
int main() {
 int arr[] = {10, 25, 30, 15, 40, 35};
 int n = sizeof(arr) / sizeof(arr[0]);
 int target = 15;
 int comparisons = 0;
 
 int result = linearSearchCount(arr, n, target, &comparisons);
 
 printf("Result: %d\n", result);
 printf("Comparisons made: %d\n", comparisons);
 
 return 0;
}
 
 Find All Occurrences 
 void linearSearchAll(int arr[], int n, int target) {
 int found = 0;
 
 printf("Element %d found at indices: ", target);
 
 for (int i = 0; i < n; i++) {
 if (arr[i] == target) {
 printf("%d ", i);
 found = 1;
 }
 }
 
 if (!found) {
 printf("Not found");
 }
 printf("\n");
}

int main() {
 int arr[] = {10, 25, 30, 25, 40, 25};
 int n = sizeof(arr) / sizeof(arr[0]);
 
 linearSearchAll(arr, n, 25);
 // Output: Element 25 found at indices: 1 3 5
 
 return 0;
}
 
 2.3 Complexity Analysis 
 
 
 
 Case 
 Time Complexity 
 Description 
 
 
 
 
 Best Case 
 O(1) 
 Element found at first position 
 
 
 Average Case 
 O(n) 
 Element found in middle 
 
 
 Worst Case 
 O(n) 
 Element at last position or not found 
 
 
 Space Complexity 
 O(1) 
 No extra space needed 
 
 
 
 Visualization: 
 Best Case (1 comparison):
[15, 25, 30, ...] → Found immediately!

Average Case (n/2 comparisons):
[10, 25, 30, 15, ...] → Found in middle

Worst Case (n comparisons):
[10, 25, 30, 40, 35, 15] → Found at end
or
[10, 25, 30, 40, 35, 20] → Not found (checked all)
 
 2.4 Advantages and Disadvantages 
 Advantages: 
 
 Simple to implement 
 Works on unsorted arrays 
 No preprocessing required 
 Works well for small datasets 
 No extra memory needed 
 
 Disadvantages: 
 
 Slow for large datasets 
 Inefficient compared to other algorithms 
 Time complexity increases linearly 
 
 When to Use: 
 
 Small datasets (n < 100) 
 Unsorted data 
 When simplicity is priority 
 When data changes frequently

3. Binary Search
3.1 Concept 
 Binary Search is a fast search algorithm that works on sorted arrays by repeatedly dividing the search interval in half. 
 Prerequisites: 
 
 Array must be sorted 
 Random access to elements (arrays work well) 
 
 How it works: 
 
 Compare target with middle element 
 If match found, return position 
 If target is smaller, search left half 
 If target is larger, search right half 
 Repeat until found or search space is empty 
 
 Visual Representation: 
 Sorted Array: [10, 15, 25, 30, 35, 40, 50]
Target: 35

Step 1: Check middle (30)
[10, 15, 25, 30, | 35, 40, 50]
 ^
35 > 30, search right half

Step 2: Check middle of right half (40)
[35, 40, 50]
 ^
35 < 40, search left half

Step 3: Check middle of remaining (35)
[35]
 ^
35 = 35, Found at index 4!
 
 3.2 Implementation 
 Iterative Binary Search 
 #include <stdio.h>

int binarySearch(int arr[], int n, int target) {
 int left = 0;
 int right = n - 1;
 
 while (left <= right) {
 int mid = left + (right - left) / 2; // Avoid overflow
 
 // Check if target is at mid
 if (arr[mid] == target) {
 return mid;
 }
 
 // If target is greater, ignore left half
 if (arr[mid] < target) {
 left = mid + 1;
 }
 // If target is smaller, ignore right half
 else {
 right = mid - 1;
 }
 }
 
 return -1; // Element not found
}

int main() {
 int arr[] = {10, 15, 25, 30, 35, 40, 50};
 int n = sizeof(arr) / sizeof(arr[0]);
 int target = 35;
 
 int result = binarySearch(arr, n, target);
 
 if (result != -1) {
 printf("Element %d found at index %d\n", target, result);
 } else {
 printf("Element %d not found\n", target);
 }
 
 return 0;
}
 
 Why mid = left + (right - left) / 2 ? 
 // This can overflow for large values:
int mid = (left + right) / 2;

// This is safer:
int mid = left + (right - left) / 2;

// Example of overflow:
// left = 2^30, right = 2^30
// (left + right) = 2^31 → overflow in 32-bit int
// left + (right - left) / 2 = no overflow
 
 Recursive Binary Search 
 int binarySearchRecursive(int arr[], int left, int right, int target) {
 // Base case: element not found
 if (left > right) {
 return -1;
 }
 
 int mid = left + (right - left) / 2;
 
 // Element found at mid
 if (arr[mid] == target) {
 return mid;
 }
 
 // Search in left half
 if (arr[mid] > target) {
 return binarySearchRecursive(arr, left, mid - 1, target);
 }
 
 // Search in right half
 return binarySearchRecursive(arr, mid + 1, right, target);
}

// Wrapper function
int binarySearch(int arr[], int n, int target) {
 return binarySearchRecursive(arr, 0, n - 1, target);
}
 
 Binary Search with Comparison Count 
 int binarySearchCount(int arr[], int n, int target, int *comparisons) {
 int left = 0;
 int right = n - 1;
 *comparisons = 0;
 
 while (left <= right) {
 int mid = left + (right - left) / 2;
 (*comparisons)++;
 
 if (arr[mid] == target) {
 return mid;
 }
 
 if (arr[mid] < target) {
 left = mid + 1;
 } else {
 right = mid - 1;
 }
 }
 
 return -1;
}

int main() {
 int arr[] = {10, 15, 25, 30, 35, 40, 50, 60, 70, 80};
 int n = sizeof(arr) / sizeof(arr[0]);
 int target = 35;
 int comparisons = 0;
 
 int result = binarySearchCount(arr, n, target, &comparisons);
 
 printf("Result: %d\n", result);
 printf("Comparisons: %d\n", comparisons);
 printf("Linear search would need: %d comparisons\n", result + 1);
 
 return 0;
}
 
 3.3 Complexity Analysis 
 
 
 
 Case 
 Time Complexity 
 Description 
 
 
 
 
 Best Case 
 O(1) 
 Element found at middle 
 
 
 Average Case 
 O(log n) 
 Typical search 
 
 
 Worst Case 
 O(log n) 
 Element at edge or not found 
 
 
 Space Complexity 
 O(1) iterative, O(log n) recursive 
 Stack space for recursion 
 
 
 
 Comparison with Linear Search: 
 Array size: 1,000,000 elements

Linear Search:
- Average: 500,000 comparisons
- Worst: 1,000,000 comparisons

Binary Search:
- Average: 20 comparisons
- Worst: 20 comparisons

Speed improvement: ~50,000x faster!
 
 Growth Comparison: 
 n Linear Search Binary Search
10 10 4
100 100 7
1,000 1,000 10
10,000 10,000 14
100,000 100,000 17
 
 3.4 Binary Search Variations 
 Find First Occurrence 
 int findFirstOccurrence(int arr[], int n, int target) {
 int left = 0;
 int right = n - 1;
 int result = -1;
 
 while (left <= right) {
 int mid = left + (right - left) / 2;
 
 if (arr[mid] == target) {
 result = mid;
 right = mid - 1; // Continue searching in left half
 }
 else if (arr[mid] < target) {
 left = mid + 1;
 }
 else {
 right = mid - 1;
 }
 }
 
 return result;
}
 
 Visual Example: 
 Array: [10, 20, 20, 20, 30, 40]
Target: 20

Regular binary search might return index 1, 2, or 3
First occurrence will always return index 1
 
 Find Last Occurrence 
 int findLastOccurrence(int arr[], int n, int target) {
 int left = 0;
 int right = n - 1;
 int result = -1;
 
 while (left <= right) {
 int mid = left + (right - left) / 2;
 
 if (arr[mid] == target) {
 result = mid;
 left = mid + 1; // Continue searching in right half
 }
 else if (arr[mid] < target) {
 left = mid + 1;
 }
 else {
 right = mid - 1;
 }
 }
 
 return result;
}
 
 Count Occurrences 
 int countOccurrences(int arr[], int n, int target) {
 int first = findFirstOccurrence(arr, n, target);
 
 if (first == -1) {
 return 0; // Element not found
 }
 
 int last = findLastOccurrence(arr, n, target);
 
 return last - first + 1;
}

int main() {
 int arr[] = {10, 20, 20, 20, 30, 40};
 int n = sizeof(arr) / sizeof(arr[0]);
 
 int count = countOccurrences(arr, n, 20);
 printf("20 occurs %d times\n", count);
 // Output: 20 occurs 3 times
 
 return 0;
}
 
 Find Insert Position 
 int searchInsertPosition(int arr[], int n, int target) {
 int left = 0;
 int right = n - 1;
 
 while (left <= right) {
 int mid = left + (right - left) / 2;
 
 if (arr[mid] == target) {
 return mid;
 }
 else if (arr[mid] < target) {
 left = mid + 1;
 }
 else {
 right = mid - 1;
 }
 }
 
 return left; // Position where target should be inserted
}

int main() {
 int arr[] = {10, 20, 30, 50, 60};
 int n = sizeof(arr) / sizeof(arr[0]);
 
 printf("Insert 25 at position: %d\n", searchInsertPosition(arr, n, 25));
 printf("Insert 35 at position: %d\n", searchInsertPosition(arr, n, 35));
 printf("Insert 70 at position: %d\n", searchInsertPosition(arr, n, 70));
 
 return 0;
}
 
 3.5 When to Use Binary Search 
 Use Binary Search when: 
 
 Data is sorted 
 Need fast searching (large datasets) 
 Data doesn't change frequently 
 Random access is available (arrays) 
 
 Don't use Binary Search when: 
 
 Data is unsorted (sorting overhead) 
 Small datasets (linear search is simpler) 
 Data changes frequently 
 Sequential access only (linked lists)

4. Introduction to Sorting
4.1 What is Sorting? 
 Sorting is the process of arranging elements in a specific order (ascending or descending). 
 Why Sort? 
 
 Faster Searching: Enables binary search 
 Data Organization: Makes data easier to understand 
 Algorithm Requirements: Many algorithms require sorted input 
 Data Presentation: Better user experience 
 Finding Duplicates: Easier with sorted data 
 
 Real-World Examples: 
 
 Sorting contacts alphabetically 
 Arranging files by date 
 Organizing products by price 
 Ranking search results 
 Leaderboards in games 
 
 4.2 Sorting Algorithm Categories 
 1. By Complexity: 
 
 Simple: Bubble, Selection, Insertion Sort - O(n²) 
 Efficient: Merge, Quick, Heap Sort - O(n log n) 
 Special: Counting, Radix, Bucket Sort - O(n) 
 
 2. By Method: 
 
 Comparison-based: Compare elements to sort 
 Non-comparison: Use element properties 
 
 3. By Stability: 
 
 Stable: Preserves relative order of equal elements 
 Unstable: May change relative order 
 
 4. By Memory: 
 
 In-place: O(1) extra space 
 Out-of-place: O(n) extra space 
 
 4.3 Sorting Algorithm Comparison Table 
 
 
 
 Algorithm 
 Best 
 Average 
 Worst 
 Space 
 Stable 
 Method 
 
 
 
 
 Bubble Sort 
 O(n) 
 O(n²) 
 O(n²) 
 O(1) 
 Yes 
 Exchange 
 
 
 Selection Sort 
 O(n²) 
 O(n²) 
 O(n²) 
 O(1) 
 No 
 Selection 
 
 
 Insertion Sort 
 O(n) 
 O(n²) 
 O(n²) 
 O(1) 
 Yes 
 Insertion 
 
 
 Merge Sort 
 O(n log n) 
 O(n log n) 
 O(n log n) 
 O(n) 
 Yes 
 Divide & Conquer 
 
 
 Quick Sort 
 O(n log n) 
 O(n log n) 
 O(n²) 
 O(log n) 
 No 
 Divide & Conquer 
 
 
 Heap Sort 
 O(n log n) 
 O(n log n) 
 O(n log n) 
 O(1) 
 No 
 Selection 
 
 
 Counting Sort 
 O(n+k) 
 O(n+k) 
 O(n+k) 
 O(k) 
 Yes 
 Non-comparison 
 
 
 Radix Sort 
 O(d(n+k)) 
 O(d(n+k)) 
 O(d(n+k)) 
 O(n+k) 
 Yes 
 Non-comparison

5. Simple Sorting Algorithms
5.1 Bubble Sort 
 Concept 
 Bubble Sort repeatedly steps through the list, compares adjacent elements, and swaps them if they're in the wrong order. 
 How it works: 
 
 Compare adjacent elements 
 Swap if in wrong order 
 Repeat for all elements 
 After each pass, largest element "bubbles" to the end 
 
 Visual Example: 
 Initial: [64, 34, 25, 12, 22, 11, 90]

Pass 1:
[34, 64, 25, 12, 22, 11, 90] → 64 > 34, swap
[34, 25, 64, 12, 22, 11, 90] → 64 > 25, swap
[34, 25, 12, 64, 22, 11, 90] → 64 > 12, swap
[34, 25, 12, 22, 64, 11, 90] → 64 > 22, swap
[34, 25, 12, 22, 11, 64, 90] → 64 > 11, swap
[34, 25, 12, 22, 11, 64, 90] → 64 < 90, no swap
→ 90 is in correct position!

Pass 2:
[25, 34, 12, 22, 11, 64, 90]
...continues until sorted...

Final: [11, 12, 22, 25, 34, 64, 90]
 
 Implementation 
 Basic Bubble Sort: 
 #include <stdio.h>

void bubbleSort(int arr[], int n) {
 for (int i = 0; i < n - 1; i++) {
 // Last i elements are already in place
 for (int j = 0; j < n - i - 1; j++) {
 // Swap if element is greater than next
 if (arr[j] > arr[j + 1]) {
 int temp = arr[j];
 arr[j] = arr[j + 1];
 arr[j + 1] = temp;
 }
 }
 }
}

void printArray(int arr[], int n) {
 for (int i = 0; i < n; i++) {
 printf("%d ", arr[i]);
 }
 printf("\n");
}

int main() {
 int arr[] = {64, 34, 25, 12, 22, 11, 90};
 int n = sizeof(arr) / sizeof(arr[0]);
 
 printf("Original array: ");
 printArray(arr, n);
 
 bubbleSort(arr, n);
 
 printf("Sorted array: ");
 printArray(arr, n);
 
 return 0;
}
 
 Optimized Bubble Sort (with flag): 
 void bubbleSortOptimized(int arr[], int n) {
 for (int i = 0; i < n - 1; i++) {
 int swapped = 0; // Flag to detect if any swap happened
 
 for (int j = 0; j < n - i - 1; j++) {
 if (arr[j] > arr[j + 1]) {
 int temp = arr[j];
 arr[j] = arr[j + 1];
 arr[j + 1] = temp;
 swapped = 1;
 }
 }
 
 // If no swaps, array is sorted
 if (swapped == 0) {
 break;
 }
 }
}
 
 Why Optimization Helps: 
 Nearly sorted array: [11, 12, 22, 25, 34, 64, 63]

Without optimization: 6 passes (always)
With optimization: 2 passes (stops when no swaps)

For already sorted array: [11, 12, 22, 25, 34, 64, 90]
Without: O(n²)
With: O(n) - only 1 pass!
 
 Bubble Sort with Visualization: 
 void bubbleSortVisualize(int arr[], int n) {
 printf("\n=== Bubble Sort Visualization ===\n");
 
 for (int i = 0; i < n - 1; i++) {
 printf("\nPass %d:\n", i + 1);
 int swapped = 0;
 
 for (int j = 0; j < n - i - 1; j++) {
 printf(" Compare %d and %d: ", arr[j], arr[j + 1]);
 
 if (arr[j] > arr[j + 1]) {
 int temp = arr[j];
 arr[j] = arr[j + 1];
 arr[j + 1] = temp;
 printf("Swap → ");
 swapped = 1;
 } else {
 printf("No swap → ");
 }
 
 printArray(arr, n);
 }
 
 if (swapped == 0) {
 printf(" Array is sorted!\n");
 break;
 }
 }
}
 
 Complexity Analysis 
 Time Complexity: 
 
 Best Case: O(n) - already sorted (with optimization) 
 Average Case: O(n²) 
 Worst Case: O(n²) - reverse sorted 
 
 Space Complexity: O(1) - in-place sorting 
 Comparisons and Swaps: 
 For array of size n:
- Comparisons: n(n-1)/2
- Swaps (worst case): n(n-1)/2

Example with n=5:
- Comparisons: 5×4/2 = 10
- Maximum swaps: 10
 
 When to Use 
 Use Bubble Sort when: 
 
 Educational purposes 
 Very small datasets (n < 10) 
 Nearly sorted data (with optimization) 
 Simplicity is priority 
 
 Don't use when: 
 
 Large datasets 
 Performance is critical 
 Production code 
 
 5.2 Selection Sort 
 Concept 
 Selection Sort divides the array into sorted and unsorted parts, repeatedly selects the minimum element from unsorted part and places it at the beginning. 
 How it works: 
 
 Find minimum element in unsorted part 
 Swap with first element of unsorted part 
 Move boundary of sorted part 
 Repeat until array is sorted 
 
 Visual Example: 
 Initial: [64, 25, 12, 22, 11]
 ↑ unsorted part

Pass 1: Find minimum (11)
[64, 25, 12, 22, 11]
 ↑ minimum
[11, 25, 12, 22, 64] → swap 11 and 64
 ↑ ↑ unsorted part
sorted

Pass 2: Find minimum (12)
[11, 25, 12, 22, 64]
 ↑ minimum
[11, 12, 25, 22, 64] → swap 12 and 25
 ↑ ↑ ↑ unsorted
 sorted

Pass 3: Find minimum (22)
[11, 12, 25, 22, 64]
 ↑ minimum
[11, 12, 22, 25, 64] → swap 22 and 25

Pass 4: Find minimum (25)
[11, 12, 22, 25, 64]
 ↑ already minimum
No swap needed

Final: [11, 12, 22, 25, 64]
 
 Implementation 
 #include <stdio.h>

void selectionSort(int arr[], int n) {
 for (int i = 0; i < n - 1; i++) {
 // Find minimum element in unsorted part
 int minIndex = i;
 
 for (int j = i + 1; j < n; j++) {
 if (arr[j] < arr[minIndex]) {
 minIndex = j;
 }
 }
 
 // Swap minimum with first element of unsorted part
 if (minIndex != i) {
 int temp = arr[i];
 arr[i] = arr[minIndex];
 arr[minIndex] = temp;
 }
 }
}

void printArray(int arr[], int n) {
 for (int i = 0; i < n; i++) {
 printf("%d ", arr[i]);
 }
 printf("\n");
}

int main() {
 int arr[] = {64, 25, 12, 22, 11};
 int n = sizeof(arr) / sizeof(arr[0]);
 
 printf("Original array: ");
 printArray(arr, n);
 
 selectionSort(arr, n);
 
 printf("Sorted array: ");
 printArray(arr, n);
 
 return 0;
}
 
 Selection Sort with Visualization: 
 void selectionSortVisualize(int arr[], int n) {
 printf("\n=== Selection Sort Visualization ===\n");
 
 for (int i = 0; i < n - 1; i++) {
 printf("\nPass %d: ", i + 1);
 
 // Print sorted part
 printf("Sorted[");
 for (int k = 0; k < i; k++) {
 printf("%d", arr[k]);
 if (k < i - 1) printf(", ");
 }
 printf("] ");
 
 int minIndex = i;
 printf("Finding minimum in unsorted part...\n");
 
 for (int j = i + 1; j < n; j++) {
 if (arr[j] < arr[minIndex]) {
 minIndex = j;
 }
 }
 
 printf(" Minimum: %d at index %d\n", arr[minIndex], minIndex);
 
 if (minIndex != i) {
 printf(" Swapping %d and %d\n", arr[i], arr[minIndex]);
 int temp = arr[i];
 arr[i] = arr[minIndex];
 arr[minIndex] = temp;
 } else {
 printf(" Already in correct position\n");
 }
 
 printf(" Result: ");
 printArray(arr, n);
 }
}
 
 Finding Maximum (Descending Order): 
 void selectionSortDescending(int arr[], int n) {
 for (int i = 0; i < n - 1; i++) {
 // Find maximum element in unsorted part
 int maxIndex = i;
 
 for (int j = i + 1; j < n; j++) {
 if (arr[j] > arr[maxIndex]) { // Changed to >
 maxIndex = j;
 }
 }
 
 // Swap
 if (maxIndex != i) {
 int temp = arr[i];
 arr[i] = arr[maxIndex];
 arr[maxIndex] = temp;
 }
 }
}
 
 Complexity Analysis 
 Time Complexity: 
 
 Best Case: O(n²) 
 Average Case: O(n²) 
 Worst Case: O(n²) 
 Always O(n²) regardless of input! 
 
 Space Complexity: O(1) - in-place sorting 
 Comparisons and Swaps: 
 For array of size n:
- Comparisons: n(n-1)/2 (always)
- Swaps: O(n) - maximum n-1 swaps

Advantage: Minimum number of swaps!
 
 Comparison with Bubble Sort: 
 Array: [5, 4, 3, 2, 1]

Bubble Sort:
- Comparisons: 10
- Swaps: 10

Selection Sort:
- Comparisons: 10
- Swaps: 2 (only swap 5↔1, then 4↔2)

→ Selection Sort better when swaps are expensive!
 
 Stability Issue 
 Selection Sort is NOT stable : 
 Input: [4a, 3, 4b, 2]
Output: [2, 3, 4b, 4a] ← Order of 4a and 4b changed!

Why? When we swap 4a with 2, 4b comes before 4a
 
 When to Use 
 Use Selection Sort when: 
 
 Swaps are expensive (writing to flash memory) 
 Small datasets 
 Memory writes must be minimized 
 Simplicity needed 
 
 Don't use when: 
 
 Stability required 
 Large datasets 
 Performance critical 
 
 5.3 Insertion Sort 
 Concept 
 Insertion Sort builds the final sorted array one item at a time by inserting each element into its correct position. 
 Analogy: Like sorting playing cards in your hand: 
 
 Pick one card at a time 
 Insert it into correct position among sorted cards 
 Shift other cards to make space 
 
 How it works: 
 
 Start with second element 
 Compare with elements in sorted part (left side) 
 Shift larger elements to the right 
 Insert element in correct position 
 Repeat for all elements 
 
 Visual Example: 
 Initial: [12, 11, 13, 5, 6]

Pass 1: Insert 11
[12, 11, 13, 5, 6]
 ↑ ↑
sorted | to insert

12 > 11, shift 12 right
[11, 12, 13, 5, 6]
 ↑ ↑
 sorted

Pass 2: Insert 13
[11, 12, 13, 5, 6]
 ↑ ↑ ↑
 sorted | to insert

13 > 12, already in position
[11, 12, 13, 5, 6]
 ↑ ↑ ↑
 sorted

Pass 3: Insert 5
[11, 12, 13, 5, 6]
 ↑ ↑ ↑ ↑
 sorted | to insert

13 > 5, shift right → [11, 12, 13, 13, 6]
12 > 5, shift right → [11, 12, 12, 13, 6]
11 > 5, shift right → [11, 11, 12, 13, 6]
Insert 5 at position 0 → [5, 11, 12, 13, 6]

Pass 4: Insert 6
[5, 11, 12, 13, 6]
 ↑ ↑ ↑ ↑ ↑
 sorted | to insert

13 > 6, shift right → [5, 11, 12, 13, 13]
12 > 6, shift right → [5, 11, 12, 12, 13]
11 > 6, shift right → [5, 11, 11, 12, 13]
5 < 6, insert at position 1 → [5, 6, 11, 12, 13]

Final: [5, 6, 11, 12, 13]
 
 Implementation 
 Basic Insertion Sort: 
 #include <stdio.h>

void insertionSort(int arr[], int n) {
 for (int i = 1; i < n; i++) {
 int key = arr[i]; // Element to be inserted
 int j = i - 1;
 
 // Move elements greater than key one position ahead
 while (j >= 0 && arr[j] > key) {
 arr[j + 1] = arr[j];
 j--;
 }
 
 // Insert key at correct position
 arr[j + 1] = key;
 }
}

void printArray(int arr[], int n) {
 for (int i = 0; i < n; i++) {
 printf("%d ", arr[i]);
 }
 printf("\n");
}

int main() {
 int arr[] = {12, 11, 13, 5, 6};
 int n = sizeof(arr) / sizeof(arr[0]);
 
 printf("Original array: ");
 printArray(arr, n);
 
 insertionSort(arr, n);
 
 printf("Sorted array: ");
 printArray(arr, n);
 
 return 0;
}
 
 Insertion Sort with Visualization: 
 void insertionSortVisualize(int arr[], int n) {
 printf("\n=== Insertion Sort Visualization ===\n");
 printf("Initial: ");
 printArray(arr, n);
 
 for (int i = 1; i < n; i++) {
 int key = arr[i];
 int j = i - 1;
 
 printf("\nPass %d: Insert %d\n", i, key);
 printf(" Sorted part: [");
 for (int k = 0; k < i; k++) {
 printf("%d", arr[k]);
 if (k < i - 1) printf(", ");
 }
 printf("]\n");
 
 int shifts = 0;
 while (j >= 0 && arr[j] > key) {
 arr[j + 1] = arr[j];
 j--;
 shifts++;
 }
 
 arr[j + 1] = key;
 
 printf(" Shifts: %d\n", shifts);
 printf(" Result: ");
 printArray(arr, n);
 }
}
 
 Descending Order: 
 void insertionSortDescending(int arr[], int n) {
 for (int i = 1; i < n; i++) {
 int key = arr[i];
 int j = i - 1;
 
 // Change condition to arr[j] < key
 while (j >= 0 && arr[j] < key) {
 arr[j + 1] = arr[j];
 j--;
 }
 
 arr[j + 1] = key;
 }
}
 
 Binary Insertion Sort (Optimization): 
 // Find position using binary search
int binarySearch(int arr[], int item, int low, int high) {
 while (low <= high) {
 int mid = low + (high - low) / 2;
 
 if (arr[mid] == item) {
 return mid + 1;
 }
 else if (arr[mid] < item) {
 low = mid + 1;
 }
 else {
 high = mid - 1;
 }
 }
 
 return low;
}

void binaryInsertionSort(int arr[], int n) {
 for (int i = 1; i < n; i++) {
 int key = arr[i];
 
 // Find position using binary search
 int pos = binarySearch(arr, key, 0, i - 1);
 
 // Shift elements
 for (int j = i - 1; j >= pos; j--) {
 arr[j + 1] = arr[j];
 }
 
 // Insert key
 arr[pos] = key;
 }
}
 
 Insertion Sort for Linked List: 
 struct Node {
 int data;
 struct Node *next;
};

void sortedInsert(struct Node **head, struct Node *newNode) {
 // If list is empty or new node should be first
 if (*head == NULL || (*head)->data >= newNode->data) {
 newNode->next = *head;
 *head = newNode;
 return;
 }
 
 // Find position to insert
 struct Node *current = *head;
 while (current->next != NULL && current->next->data < newNode->data) {
 current = current->next;
 }
 
 newNode->next = current->next;
 current->next = newNode;
}

void insertionSortList(struct Node **head) {
 struct Node *sorted = NULL;
 struct Node *current = *head;
 
 while (current != NULL) {
 struct Node *next = current->next;
 sortedInsert(&sorted, current);
 current = next;
 }
 
 *head = sorted;
}
 
 Complexity Analysis 
 Time Complexity: 
 
 Best Case: O(n) - already sorted 
 Average Case: O(n²) 
 Worst Case: O(n²) - reverse sorted 
 
 Space Complexity: O(1) - in-place sorting 
 Detailed Analysis: 
 Best Case (sorted): [1, 2, 3, 4, 5]
- Comparisons: n-1 (each element compared once)
- Shifts: 0
- Time: O(n)

Worst Case (reverse sorted): [5, 4, 3, 2, 1]
- Comparisons: 1+2+3+...+(n-1) = n(n-1)/2
- Shifts: Same as comparisons
- Time: O(n²)

Average Case (random):
- Comparisons: ~n²/4
- Shifts: ~n²/4
- Time: O(n²)
 
 Performance on Different Inputs: 
 void testInsertionSort() {
 // Already sorted
 int sorted[] = {1, 2, 3, 4, 5};
 printf("Sorted array: Fast! O(n)\n");
 
 // Reverse sorted
 int reverse[] = {5, 4, 3, 2, 1};
 printf("Reverse array: Slow! O(n²)\n");
 
 // Nearly sorted
 int nearlySorted[] = {1, 2, 4, 3, 5};
 printf("Nearly sorted: Fast! O(n)\n");
 
 // Few elements out of place
 int fewMoves[] = {2, 1, 3, 4, 5};
 printf("Few out of place: Fast!\n");
}
 
 Advantages 
 
 Simple implementation 
 Stable - preserves relative order 
 In-place - O(1) extra space 
 Adaptive - O(n) for nearly sorted data 
 Online - can sort as data arrives 
 
 Stability Example: 
 Input: [4a, 3, 4b, 2]
Output: [2, 3, 4a, 4b] ← Order preserved!
 
 When to Use 
 Use Insertion Sort when: 
 
 Small datasets (n < 50) 
 Nearly sorted data 
 Stability required 
 Online sorting (data arriving in real-time) 
 Linked lists (no shifting overhead) 
 
 Don't use when: 
 
 Large datasets 
 Random data 
 Performance critical 
 
 Real-World Applications: 
 
 Sorting small files 
 Hybrid sorting (used in TimSort) 
 Online algorithms 
 Sorting linked lists

6. Efficient Sorting Algorithms
6.1 Merge Sort 
 Concept 
 Merge Sort is a divide-and-conquer algorithm that divides the array into halves, recursively sorts them, and then merges the sorted halves. 
 Divide and Conquer Strategy: 
 
 Divide: Split array into two halves 
 Conquer: Recursively sort each half 
 Combine: Merge the two sorted halves 
 
 Visual Example: 
 Initial Array: [38, 27, 43, 3, 9, 82, 10]

DIVIDE Phase:
 [38, 27, 43, 3, 9, 82, 10]
 / \
 [38, 27, 43, 3] [9, 82, 10]
 / \ / \
 [38, 27] [43, 3] [9, 82] [10]
 / \ / \ / \ |
 [38] [27] [43] [3] [9] [82] [10]

MERGE Phase:
 [38] [27] [43] [3] [9] [82] [10]
 \ / \ / \ / |
 [27, 38] [3, 43] [9, 82] [10]
 \ / \ /
 [3, 27, 38, 43] [9, 10, 82]
 \ /
 [3, 9, 10, 27, 38, 43, 82]
 
 Implementation 
 Merge Sort Algorithm: 
 #include <stdio.h>
#include <stdlib.h>

// Merge two sorted subarrays
void merge(int arr[], int left, int mid, int right) {
 int n1 = mid - left + 1; // Size of left subarray
 int n2 = right - mid; // Size of right subarray
 
 // Create temporary arrays
 int *L = (int*)malloc(n1 * sizeof(int));
 int *R = (int*)malloc(n2 * sizeof(int));
 
 // Copy data to temporary arrays
 for (int i = 0; i < n1; i++) {
 L[i] = arr[left + i];
 }
 for (int j = 0; j < n2; j++) {
 R[j] = arr[mid + 1 + j];
 }
 
 // Merge the temporary arrays back
 int i = 0; // Initial index of left subarray
 int j = 0; // Initial index of right subarray
 int k = left; // Initial index of merged array
 
 while (i < n1 && j < n2) {
 if (L[i] <= R[j]) {
 arr[k] = L[i];
 i++;
 } else {
 arr[k] = R[j];
 j++;
 }
 k++;
 }
 
 // Copy remaining elements of L[]
 while (i < n1) {
 arr[k] = L[i];
 i++;
 k++;
 }
 
 // Copy remaining elements of R[]
 while (j < n2) {
 arr[k] = R[j];
 j++;
 k++;
 }
 
 free(L);
 free(R);
}

// Main merge sort function
void mergeSort(int arr[], int left, int right) {
 if (left < right) {
 int mid = left + (right - left) / 2;
 
 // Sort first half
 mergeSort(arr, left, mid);
 
 // Sort second half
 mergeSort(arr, mid + 1, right);
 
 // Merge the sorted halves
 merge(arr, left, mid, right);
 }
}

void printArray(int arr[], int n) {
 for (int i = 0; i < n; i++) {
 printf("%d ", arr[i]);
 }
 printf("\n");
}

int main() {
 int arr[] = {38, 27, 43, 3, 9, 82, 10};
 int n = sizeof(arr) / sizeof(arr[0]);
 
 printf("Original array: ");
 printArray(arr, n);
 
 mergeSort(arr, 0, n - 1);
 
 printf("Sorted array: ");
 printArray(arr, n);
 
 return 0;
}
 
 Merge Sort with Visualization: 
 void mergeSortVisualize(int arr[], int left, int right, int depth) {
 if (left < right) {
 // Print indentation based on recursion depth
 for (int i = 0; i < depth; i++) printf(" ");
 
 printf("Divide: [");
 for (int i = left; i <= right; i++) {
 printf("%d", arr[i]);
 if (i < right) printf(", ");
 }
 printf("]\n");
 
 int mid = left + (right - left) / 2;
 
 mergeSortVisualize(arr, left, mid, depth + 1);
 mergeSortVisualize(arr, mid + 1, right, depth + 1);
 
 merge(arr, left, mid, right);
 
 // Print result after merge
 for (int i = 0; i < depth; i++) printf(" ");
 printf("Merge: [");
 for (int i = left; i <= right; i++) {
 printf("%d", arr[i]);
 if (i < right) printf(", ");
 }
 printf("]\n");
 }
}
 
 Iterative Merge Sort: 
 void mergeSortIterative(int arr[], int n) {
 // Start with merge subarrays of size 1, then 2, 4, 8, ...
 for (int currSize = 1; currSize < n; currSize *= 2) {
 // Pick starting index of left sub array
 for (int leftStart = 0; leftStart < n - 1; leftStart += 2 * currSize) {
 // Find ending point of left subarray
 int mid = leftStart + currSize - 1;
 
 // Find ending point of right subarray
 int rightEnd = (leftStart + 2 * currSize - 1 < n - 1) ?
 leftStart + 2 * currSize - 1 : n - 1;
 
 // Merge subarrays
 if (mid < rightEnd) {
 merge(arr, leftStart, mid, rightEnd);
 }
 }
 }
}
 
 Complexity Analysis 
 Time Complexity: 
 
 Best Case: O(n log n) 
 Average Case: O(n log n) 
 Worst Case: O(n log n) 
 Always O(n log n)! 
 
 Space Complexity: O(n) - requires temporary arrays 
 Why O(n log n)? 
 Tree height: log₂(n) levels
Work at each level: n comparisons/copies

Total work = height × work per level
 = log₂(n) × n
 = O(n log n)

Example with n=8:
Level 0: [8 elements] → n operations
Level 1: [4,4] → n operations (4+4)
Level 2: [2,2,2,2] → n operations (2+2+2+2)
Level 3: [1,1,1,1,1,1,1,1] → n operations

Total levels = log₂(8) = 3
Total operations = 3n = O(n log n)
 
 Comparison with Simple Sorts: 
 n=1,000:
- Insertion Sort: ~500,000 operations
- Merge Sort: ~10,000 operations
→ 50x faster!

n=1,000,000:
- Insertion Sort: ~500 billion operations
- Merge Sort: ~20 million operations
→ 25,000x faster!
 
 Advantages and Disadvantages 
 Advantages: 
 
 Guaranteed O(n log n) - always efficient 
 Stable - preserves relative order 
 Predictable - no worst-case scenarios 
 Good for linked lists - O(1) space possible 
 Parallelizable - can sort halves independently 
 
 Disadvantages: 
 
 O(n) space - requires temporary storage 
 Not in-place - not memory efficient 
 Overhead - slower than Quick Sort in practice 
 Not adaptive - doesn't benefit from sorted data 
 
 When to Use 
 Use Merge Sort when: 
 
 Guaranteed O(n log n) required 
 Stability is important 
 Working with linked lists 
 External sorting (large files) 
 Parallel processing available 
 
 Don't use when: 
 
 Memory is limited 
 In-place sorting required 
 Small datasets (overhead not worth it) 
 
 6.2 Quick Sort 
 Concept 
 Quick Sort is a divide-and-conquer algorithm that picks a pivot element and partitions the array around it, then recursively sorts the subarrays. 
 How it works: 
 
 Choose Pivot: Select an element as pivot 
 Partition: Rearrange so elements < pivot are left, elements > pivot are right 
 Recursively sort: Sort left and right subarrays 
 
 Visual Example: 
 Initial: [10, 80, 30, 90, 40, 50, 70]
 Pick pivot = 70 (last element)

Partition:
[10, 30, 40, 50] 70 [80, 90]
 ← less than 70 greater than 70 →

Recursively sort left: [10, 30, 40, 50]
Pick pivot = 50
[10, 30, 40] 50 []

Recursively sort right: [80, 90]
Pick pivot = 90
[80] 90 []

Final: [10, 30, 40, 50, 70, 80, 90]
 
 Partitioning Process: 
 Array: [10, 80, 30, 90, 40, 50, 70]
Pivot: 70 (last element)

i = -1 (tracks position of smaller elements)
j = 0 (scans through array)

j=0: arr[0]=10 < 70 → swap arr[++i] with arr[j]
 [10, 80, 30, 90, 40, 50, 70]
 i

j=1: arr[1]=80 > 70 → no swap
 [10, 80, 30, 90, 40, 50, 70]
 i

j=2: arr[2]=30 < 70 → swap arr[++i] with arr[j]
 [10, 30, 80, 90, 40, 50, 70]
 i

j=3: arr[3]=90 > 70 → no swap

j=4: arr[4]=40 < 70 → swap arr[++i] with arr[j]
 [10, 30, 40, 90, 80, 50, 70]
 i

j=5: arr[5]=50 < 70 → swap arr[++i] with arr[j]
 [10, 30, 40, 50, 80, 90, 70]
 i

Finally: Place pivot at i+1
 [10, 30, 40, 50, 70, 90, 80]
 ↑
 pivot in place
 
 Implementation 
 Quick Sort with Last Element as Pivot: 
 #include <stdio.h>

// Swap two elements
void swap(int *a, int *b) {
 int temp = *a;
 *a = *b;
 *b = temp;
}

// Partition function
int partition(int arr[], int low, int high) {
 int pivot = arr[high]; // Choose last element as pivot
 int i = low - 1; // Index of smaller element
 
 for (int j = low; j < high; j++) {
 // If current element is smaller than pivot
 if (arr[j] < pivot) {
 i++;
 swap(&arr[i], &arr[j]);
 }
 }
 
 // Place pivot in correct position
 swap(&arr[i + 1], &arr[high]);
 return i + 1;
}

// Quick sort function
void quickSort(int arr[], int low, int high) {
 if (low < high) {
 // Partition index
 int pi = partition(arr, low, high);
 
 // Recursively sort elements before and after partition
 quickSort(arr, low, pi - 1);
 quickSort(arr, pi + 1, high);
 }
}

void printArray(int arr[], int n) {
 for (int i = 0; i < n; i++) {
 printf("%d ", arr[i]);
 }
 printf("\n");
}

int main() {
 int arr[] = {10, 80, 30, 90, 40, 50, 70};
 int n = sizeof(arr) / sizeof(arr[0]);
 
 printf("Original array: ");
 printArray(arr, n);
 
 quickSort(arr, 0, n - 1);
 
 printf("Sorted array: ");
 printArray(arr, n);
 
 return 0;
}
 
 Quick Sort with Middle Element as Pivot: 
 int partitionMiddle(int arr[], int low, int high) {
 int mid = low + (high - low) / 2;
 int pivot = arr[mid];
 
 // Move pivot to end
 swap(&arr[mid], &arr[high]);
 
 int i = low - 1;
 
 for (int j = low; j < high; j++) {
 if (arr[j] < pivot) {
 i++;
 swap(&arr[i], &arr[j]);
 }
 }
 
 swap(&arr[i + 1], &arr[high]);
 return i + 1;
}
 
 Quick Sort with Random Pivot: 
 #include <stdlib.h>
#include <time.h>

int partitionRandom(int arr[], int low, int high) {
 // Generate random pivot index
 srand(time(NULL));
 int randomIndex = low + rand() % (high - low + 1);
 
 // Move pivot to end
 swap(&arr[randomIndex], &arr[high]);
 
 return partition(arr, low, high);
}

void quickSortRandom(int arr[], int low, int high) {
 if (low < high) {
 int pi = partitionRandom(arr, low, high);
 quickSortRandom(arr, low, pi - 1);
 quickSortRandom(arr, pi + 1, high);
 }
}
 
 Quick Sort with Visualization: 
 void quickSortVisualize(int arr[], int low, int high, int depth) {
 if (low < high) {
 // Print indentation
 for (int i = 0; i < depth; i++) printf(" ");
 
 printf("Sorting: [");
 for (int i = low; i <= high; i++) {
 printf("%d", arr[i]);
 if (i < high) printf(", ");
 }
 printf("] Pivot=%d\n", arr[high]);
 
 int pi = partition(arr, low, high);
 
 // Print result
 for (int i = 0; i < depth; i++) printf(" ");
 printf("Result: [");
 for (int i = low; i <= high; i++) {
 if (i == pi) printf("*");
 printf("%d", arr[i]);
 if (i == pi) printf("*");
 if (i < high) printf(", ");
 }
 printf("]\n");
 
 quickSortVisualize(arr, low, pi - 1, depth + 1);
 quickSortVisualize(arr, pi + 1, high, depth + 1);
 }
}
 
 Three-Way Partitioning (for duplicates): 
 void quickSort3Way(int arr[], int low, int high) {
 if (low >= high) return;
 
 int pivot = arr[high];
 int i = low;
 int lt = low; // Elements < pivot
 int gt = high; // Elements > pivot
 
 while (i <= gt) {
 if (arr[i] < pivot) {
 swap(&arr[lt++], &arr[i++]);
 }
 else if (arr[i] > pivot) {
 swap(&arr[i], &arr[gt--]);
 }
 else {
 i++;
 }
 }
 
 quickSort3Way(arr, low, lt - 1);
 quickSort3Way(arr, gt + 1, high);
}
 
 Complexity Analysis 
 Time Complexity: 
 
 Best Case: O(n log n) - balanced partitions 
 Average Case: O(n log n) 
 Worst Case: O(n²) - unbalanced partitions 
 
 Space Complexity: O(log n) - recursion stack 
 Best Case (Balanced Partition): 
 Each partition divides array in half

 [8 elements]
 / \
 [4] [4]
 / \ / \
 [2] [2] [2] [2]
 / \ / \ / \ / \
[1][1][1][1] [1][1][1][1]

Height = log₂(n)
Work per level = n
Total = O(n log n)
 
 Worst Case (Unbalanced Partition): 
 Sorted or reverse sorted with bad pivot choice

[5, 4, 3, 2, 1] pivot = 1
 ↓
[1] [5, 4, 3, 2] pivot = 2
 ↓
 [2] [5, 4, 3] pivot = 3
 ↓
 [3] [5, 4]
 ↓
 [4] [5]

Height = n
Work = n + (n-1) + (n-2) + ... + 1
 = n(n+1)/2
 = O(n²)
 
 Avoiding Worst Case: 
 
 Random Pivot: Makes worst case unlikely 
 Median-of-Three: Use median of first, middle, last 
 Three-Way Partition: Handle duplicates efficiently 
 
 Advantages and Disadvantages 
 Advantages: 
 
 Fast in practice - usually faster than Merge Sort 
 In-place - O(log n) space only 
 Cache-friendly - good locality of reference 
 Parallelizable - can sort partitions independently 
 
 Disadvantages: 
 
 Unstable - doesn't preserve relative order 
 O(n²) worst case - rare but possible 
 Not adaptive - doesn't benefit from sorted data 
 Recursive - stack overflow for deep recursion 
 
 Pivot Selection Strategies 
 1. Last Element (Simple): 
 int pivot = arr[high];
 
 
 Simple but vulnerable to sorted input 
 
 2. First Element: 
 int pivot = arr[low];
 
 
 Same issue as last element 
 
 3. Middle Element: 
 int mid = low + (high - low) / 2;
int pivot = arr[mid];
 
 
 Better for sorted input 
 
 4. Random Element: 
 int randomIndex = low + rand() % (high - low + 1);
int pivot = arr[randomIndex];
 
 
 Probabilistically avoids worst case 
 
 5. Median-of-Three: 
 int medianOfThree(int arr[], int low, int high) {
 int mid = low + (high - low) / 2;
 
 if (arr[low] > arr[mid])
 swap(&arr[low], &arr[mid]);
 if (arr[low] > arr[high])
 swap(&arr[low], &arr[high]);
 if (arr[mid] > arr[high])
 swap(&arr[mid], &arr[high]);
 
 return mid;
}
 
 
 Best practical choice 
 
 When to Use 
 Use Quick Sort when: 
 
 Average case performance matters 
 Memory is limited (in-place) 
 Cache performance important 
 Large datasets 
 Stability not required 
 
 Don't use when: 
 
 Worst case must be avoided 
 Stability required 
 Small datasets 
 Stack space is limited 
 
 Comparison with Merge Sort: 
 Quick Sort Merge Sort
Time (avg): O(n log n) O(n log n)
Time (worst): O(n²) O(n log n)
Space: O(log n) O(n)
Stable: No Yes
In-place: Yes No
Cache: Better Worse
Practice: Faster Slower

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

8. Practical Applications
8.1 Search and Sort Combined 
 #include <stdio.h>
#include <stdlib.h>
#include <string.h>

// Student structure
typedef struct {
 int id;
 char name[50];
 float gpa;
} Student;

// Compare functions for sorting
int compareByID(const void *a, const void *b) {
 return ((Student*)a)->id - ((Student*)b)->id;
}

int compareByGPA(const void *a, const void *b) {
 float diff = ((Student*)b)->gpa - ((Student*)a)->gpa;
 return (diff > 0) ? 1 : (diff < 0) ? -1 : 0;
}

int compareByName(const void *a, const void *b) {
 return strcmp(((Student*)a)->name, ((Student*)b)->name);
}

// Binary search by ID
int searchByID(Student students[], int n, int targetID) {
 int left = 0, right = n - 1;
 
 while (left <= right) {
 int mid = left + (right - left) / 2;
 
 if (students[mid].id == targetID) {
 return mid;
 }
 else if (students[mid].id < targetID) {
 left = mid + 1;
 }
 else {
 right = mid - 1;
 }
 }
 
 return -1;
}

// Linear search by name
int searchByName(Student students[], int n, const char *name) {
 for (int i = 0; i < n; i++) {
 if (strcmp(students[i].name, name) == 0) {
 return i;
 }
 }
 return -1;
}

// Print students
void printStudents(Student students[], int n) {
 printf("\n%-10s %-20s %-8s\n", "ID", "Name", "GPA");
 printf("----------------------------------------\n");
 for (int i = 0; i < n; i++) {
 printf("%-10d %-20s %.2f\n", 
 students[i].id, students[i].name, students[i].gpa);
 }
}

int main() {
 Student students[] = {
 {1003, "Alice Johnson", 3.8},
 {1001, "Bob Smith", 3.5},
 {1005, "Charlie Brown", 3.9},
 {1002, "Diana Prince", 3.7},
 {1004, "Eve Wilson", 3.6}
 };
 int n = sizeof(students) / sizeof(students[0]);
 
 printf("=== Student Database ===\n");
 printf("\nOriginal Data:");
 printStudents(students, n);
 
 // Sort by ID
 qsort(students, n, sizeof(Student), compareByID);
 printf("\nSorted by ID:");
 printStudents(students, n);
 
 // Search by ID
 int targetID = 1003;
 int index = searchByID(students, n, targetID);
 if (index != -1) {
 printf("\nStudent with ID %d: %s (GPA: %.2f)\n", 
 targetID, students[index].name, students[index].gpa);
 }
 
 // Sort by GPA (descending)
 qsort(students, n, sizeof(Student), compareByGPA);
 printf("\nSorted by GPA (highest first):");
 printStudents(students, n);
 
 // Sort by Name
 qsort(students, n, sizeof(Student), compareByName);
 printf("\nSorted by Name:");
 printStudents(students, n);
 
 return 0;
}
 
 8.2 Finding Kth Largest Element 
 // Partition function (same as Quick Sort)
int partition(int arr[], int low, int high) {
 int pivot = arr[high];
 int i = low - 1;
 
 for (int j = low; j < high; j++) {
 if (arr[j] <= pivot) {
 i++;
 int temp = arr[i];
 arr[i] = arr[j];
 arr[j] = temp;
 }
 }
 
 int temp = arr[i + 1];
 arr[i + 1] = arr[high];
 arr[high] = temp;
 
 return i + 1;
}

// Quick Select algorithm - O(n) average time
int findKthLargest(int arr[], int low, int high, int k) {
 if (low == high) {
 return arr[low];
 }
 
 int pi = partition(arr, low, high);
 int length = high - pi + 1;
 
 if (length == k) {
 return arr[pi];
 }
 else if (length > k) {
 return findKthLargest(arr, pi + 1, high, k);
 }
 else {
 return findKthLargest(arr, low, pi - 1, k - length);
 }
}

int main() {
 int arr[] = {3, 2, 1, 5, 6, 4};
 int n = sizeof(arr) / sizeof(arr[0]);
 int k = 2;
 
 int result = findKthLargest(arr, 0, n - 1, k);
 printf("%dth largest element: %d\n", k, result);
 // Output: 2nd largest element: 5
 
 return 0;
}
 
 8.3 Merge Two Sorted Arrays 
 #include <stdio.h>
#include <stdlib.h>

int* mergeSortedArrays(int arr1[], int n1, int arr2[], int n2) {
 int *result = (int*)malloc((n1 + n2) * sizeof(int));
 int i = 0, j = 0, k = 0;
 
 // Merge while both arrays have elements
 while (i < n1 && j < n2) {
 if (arr1[i] <= arr2[j]) {
 result[k++] = arr1[i++];
 } else {
 result[k++] = arr2[j++];
 }
 }
 
 // Copy remaining elements from arr1
 while (i < n1) {
 result[k++] = arr1[i++];
 }
 
 // Copy remaining elements from arr2
 while (j < n2) {
 result[k++] = arr2[j++];
 }
 
 return result;
}

int main() {
 int arr1[] = {1, 3, 5, 7};
 int arr2[] = {2, 4, 6, 8};
 int n1 = sizeof(arr1) / sizeof(arr1[0]);
 int n2 = sizeof(arr2) / sizeof(arr2[0]);
 
 int *merged = mergeSortedArrays(arr1, n1, arr2, n2);
 
 printf("Merged array: ");
 for (int i = 0; i < n1 + n2; i++) {
 printf("%d ", merged[i]);
 }
 printf("\n");
 
 free(merged);
 return 0;
}
 
 8.4 Finding Median 
 // Find median of unsorted array
double findMedian(int arr[], int n) {
 // Sort the array first
 quickSort(arr, 0, n - 1);
 
 // Find median
 if (n % 2 == 0) {
 // Even number of elements - average of two middle
 return (arr[n/2 - 1] + arr[n/2]) / 2.0;
 } else {
 // Odd number of elements - middle element
 return arr[n/2];
 }
}

int main() {
 int arr1[] = {3, 1, 4, 1, 5, 9, 2};
 int arr2[] = {6, 5, 3, 5, 8, 9};
 
 printf("Median of arr1: %.1f\n", findMedian(arr1, 7));
 printf("Median of arr2: %.1f\n", findMedian(arr2, 6));
 
 return 0;
}
 
 8.5 Removing Duplicates from Sorted Array 
 int removeDuplicates(int arr[], int n) {
 if (n == 0 || n == 1) {
 return n;
 }
 
 int j = 0; // Index for unique elements
 
 for (int i = 0; i < n - 1; i++) {
 if (arr[i] != arr[i + 1]) {
 arr[j++] = arr[i];
 }
 }
 
 arr[j++] = arr[n - 1]; // Add last element
 
 return j; // New length
}

int main() {
 int arr[] = {1, 1, 2, 2, 2, 3, 4, 4, 5};
 int n = sizeof(arr) / sizeof(arr[0]);
 
 printf("Original: ");
 for (int i = 0; i < n; i++) {
 printf("%d ", arr[i]);
 }
 printf("\n");
 
 int newLength = removeDuplicates(arr, n);
 
 printf("After removing duplicates: ");
 for (int i = 0; i < newLength; i++) {
 printf("%d ", arr[i]);
 }
 printf("\n");
 
 return 0;
}
 
 8.6 Finding Intersection of Two Arrays 
 void findIntersection(int arr1[], int n1, int arr2[], int n2) {
 // Sort both arrays first
 quickSort(arr1, 0, n1 - 1);
 quickSort(arr2, 0, n2 - 1);
 
 printf("Intersection: ");
 int i = 0, j = 0;
 
 while (i < n1 && j < n2) {
 if (arr1[i] < arr2[j]) {
 i++;
 }
 else if (arr1[i] > arr2[j]) {
 j++;
 }
 else {
 // Elements are equal
 printf("%d ", arr1[i]);
 i++;
 j++;
 }
 }
 printf("\n");
}

int main() {
 int arr1[] = {1, 3, 4, 5, 7};
 int arr2[] = {2, 3, 5, 6};
 
 findIntersection(arr1, 5, arr2, 4);
 // Output: Intersection: 3 5
 
 return 0;
}
 
 8.7 Sorting Strings 
 #include <stdio.h>
#include <string.h>

void sortStrings(char *arr[], int n) {
 for (int i = 0; i < n - 1; i++) {
 for (int j = 0; j < n - i - 1; j++) {
 if (strcmp(arr[j], arr[j + 1]) > 0) {
 // Swap pointers
 char *temp = arr[j];
 arr[j] = arr[j + 1];
 arr[j + 1] = temp;
 }
 }
 }
}

int main() {
 char *fruits[] = {"Banana", "Apple", "Orange", "Mango", "Grape"};
 int n = 5;
 
 printf("Original: ");
 for (int i = 0; i < n; i++) {
 printf("%s ", fruits[i]);
 }
 printf("\n");
 
 sortStrings(fruits, n);
 
 printf("Sorted: ");
 for (int i = 0; i < n; i++) {
 printf("%s ", fruits[i]);
 }
 printf("\n");
 
 return 0;
}