Introduction to Sorting

In sorting algorithms, the primary goal is to arrange elements in a certain order, usually numerical or lexicographical. Sorting is a fundamental operation in computer science, with applications in database indexing, searching algorithms, and even hardware optimization. To understand sorting thoroughly, it’s essential to analyze its performance, particularly in terms of time complexity.

Time Complexity: \(O(n^2)\) vs \(O(n \log n)\)

Time complexity helps us measure the number of operations an algorithm takes to complete, based on the size of the input, denoted as \(n\). For sorting, common algorithms fall into two broad categories:

• Quadratic Time (\(O(n^2)\)): Simple sorting algorithms such as Bubble Sort, Insertion Sort, and Selection Sort have time complexities of \(O(n^2)\). This means the time taken grows quadratically as the input size increases. For larger datasets, these algorithms tend to be inefficient due to the nested loops involved in their comparisons and swaps.

• Log-Linear Time (\(O(n \log n)\)): More efficient algorithms like Merge Sort, Quick Sort, and Heap Sort fall under this category. These algorithms leverage divide-and-conquer or heap structures to reduce the number of comparisons needed. Their time complexity reflects the logarithmic factor introduced by dividing the problem into smaller subproblems, making them suitable for handling larger datasets efficiently.

Why Sorting Cannot Be Faster than \(O(n \log n)\)

Intuitively, sorting can’t be faster than \(O(n \log n)\) for comparison-based algorithms. This is due to the fact that, in comparison-based sorting, we need to compare pairs of elements to determine their relative order. There are \(n!\) (factorial of \(n\)) possible ways to arrange \(n\) elements, and to differentiate between them, at least \( \log(n!) \) comparisons are required. Using Stirling’s approximation, \( \log(n!) \) simplifies to \( O(n \log n) \) . Hence, no comparison-based algorithm can sort more efficiently than this bound.

Bubble Sort

Bubble Sort is a simple comparison-based sorting algorithm. It works by repeatedly stepping through the list, comparing adjacent elements and swapping them if they are in the wrong order. This process is repeated until the list is sorted.

Strategy of Bubble Sort

Bubble Sort repeatedly compares pairs of adjacent elements and swaps them if they are in the wrong order. The largest unsorted element "bubbles" to the end of the list with each pass, which is why it's called Bubble Sort.

Steps:

1. Start at the beginning of the list.

2. Compare the first two elements.

3. If the first element is greater than the second, swap them.

4. Move to the next adjacent pair (second and third) and repeat step 3.

5. Continue this process until the end of the list.

6. The largest element will have bubbled to the last position.

7. Ignore the last element and repeat the process for the remaining unsorted portion of the list.

8. Continue until no more swaps are needed.

Inner Loop Behavior

The inner loop doesn't always start from the beginning after each pass because after each pass, the largest element gets placed at the correct position at the end of the list. Therefore, it is unnecessary to compare it again in subsequent passes. Thus, the inner loop will traverse fewer elements as the algorithm progresses.

Example of Bubble Sort

Let’s consider an array: [5, 1, 4, 2, 8].

Initial State:

[5, 1, 4, 2, 8]

Pass 1:

Compare 5 and 1: Swap,  [1, 5, 4, 2, 8]
Compare 5 and 4: Swap,  [1, 4, 5, 2, 8]
Compare 5 and 2: Swap,  [1, 4, 2, 5, 8]
Compare 5 and 8: No Swap

End of Pass 1, largest element 8 is in its correct place.

Pass 2:

Compare 1 and 4: No Swap
Compare 4 and 2: Swap,  [1, 2, 4, 5, 8]
Compare 4 and 5: No Swap

End of Pass 2, 5 is now in its correct place.

Pass 3:

Compare 1 and 2: No Swap
Compare 2 and 4: No Swap

End of Pass 3, no more swaps needed, the list is sorted.

Final sorted array:

[1, 2, 4, 5, 8]

C Code for Bubble Sort

#include <stdio.h>

void bubbleSort(int arr[], int n) {
    int i, j;
    for (i = 0; i < n-1; i++) {
        int swapped = 0; // To optimize if the array is already sorted
        for (j = 0; j < n-i-1; j++) {
            if (arr[j] > arr[j+1]) {
                // Swap arr[j] and arr[j+1]
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                swapped = 1; // Mark that we made a swap
            }
        }
        // If no elements were swapped, break
        if (swapped == 0) {
            break;
        }
    }
}

void printArray(int arr[], int size) {
    for (int i = 0; i < size; 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("Unsorted array: \n");
    printArray(arr, n);
    bubbleSort(arr, n);
    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;
}

Explanation of the C Code

• bubbleSort function: This function takes an array and its size as input and sorts the array using Bubble Sort.

  • The outer loop (i) iterates from 0 to n-1, representing the number of passes.

  • The inner loop (j) iterates through the array up to the last unsorted element (n-i-1), performing the comparison and swap.

  • The swapped flag is introduced to detect if a swap occurred during the pass. If no swaps happen, it means the array is already sorted, and we can exit early.

• printArray function: This utility function prints the array before and after sorting.

• main function: This function defines an array, prints the unsorted version, calls the bubbleSort function, and then prints the sorted array.

Time Complexity of Bubble Sort

Worst Case: \( O(n^2) \)

In the worst case, Bubble Sort must perform \(n-1\) passes, and for each pass, it compares \(n-i-1\) elements. This results in a total of \(O(n^2)\) comparisons and swaps.

Best Case: \( O(n) \)

In the best case, when the array is already sorted, the algorithm still checks each adjacent pair but makes no swaps. If the swapped flag is used as in the code above, the algorithm exits after the first pass, leading to a time complexity of \(O(n)\).

Average Case: \( O(n^2) \)

On average, the time complexity remains \(O(n^2)\) since the algorithm doesn't have any knowledge of the initial arrangement of elements and must compare them in each pass.

Insertion Sort

Insertion Sort is a simple, comparison-based sorting algorithm that works similarly to how you would sort playing cards in your hands. It builds the sorted array one element at a time by repeatedly inserting unsorted elements into their correct positions in the already sorted part of the array.

Strategy of Insertion Sort

Insertion Sort works by dividing the array into a "sorted" and "unsorted" part. Initially, the sorted part contains only the first element, and as we move through the array, we take the next unsorted element and insert it into its correct position in the sorted part. The insertion is done by shifting elements that are greater than the current element to the right until the correct position is found.

Steps:

1. Start with the second element in the array, since a single element is trivially sorted.

2. Compare the current element with the elements in the sorted part of the array.

3. If the current element is smaller than any of the elements in the sorted part, shift the larger elements to the right to make room.

4. Insert the current element in the correct position.

5. Repeat the process for each element until the array is fully sorted.

Inner Loop Behavior

The inner loop is the heart of the Insertion Sort algorithm. It iterates backward through the sorted portion of the array to find the correct position for the current element. What’s special is that, in the worst case, the inner loop may need to shift multiple elements to the right to make space for the current element.

Example of Insertion Sort

Let’s consider an array: [5, 2, 9, 1, 5, 6].

Initial State:

[5, 2, 9, 1, 5, 6]

Pass 1 (Compare and Insert 2):

• Sorted part: [5]

• Compare 5 and 2: Shift 5 right

• Insert 2 at the start

[2, 5, 9, 1, 5, 6]

Pass 2 (Compare and Insert 9):

• Sorted part: [2, 5]

• Compare 9 and 5: No shift needed

• 9 remains in place

[2, 5, 9, 1, 5, 6]

Pass 3 (Compare and Insert 1):

• Sorted part: [2, 5, 9]

• Compare 9 and 1: Shift 9 right

• Compare 5 and 1: Shift 5 right

• Compare 2 and 1: Shift 2 right

• Insert 1 at the start

[1, 2, 5, 9, 5, 6]

Pass 4 (Compare and Insert 5):

• Sorted part: [1, 2, 5, 9]

• Compare 9 and 5: Shift 9 right

• Insert 5 between the two 5s

[1, 2, 5, 5, 9, 6]

Pass 5 (Compare and Insert 6):

• Sorted part: [1, 2, 5, 5, 9]

• Compare 9 and 6: Shift 9 right

• Insert 6 before 9

[1, 2, 5, 5, 6, 9]

Final sorted array:

[1, 2, 5, 5, 6, 9]

C Code for Insertion Sort

#include <stdio.h>

void insertionSort(int arr[], int n) {
    int i, key, j;
    for (i = 1; i < n; i++) {
        key = arr[i]; // The current element to be inserted
        j = i - 1;

        // Move elements of arr[0..i-1], that are greater than key,
        // to one position ahead of their current position
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key; // Insert key in the correct position
    }
}

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("Unsorted array: \n");
    printArray(arr, n);

    insertionSort(arr, n);

    printf("Sorted array: \n");
    printArray(arr, n);

    return 0;
}

Explanation of the C Code

• insertionSort function: This function implements the Insertion Sort algorithm.

  • The outer loop starts at the second element and runs until the last element of the array.

  • The variable key holds the element to be inserted into the sorted portion.

  • The inner while loop finds the correct position for key by shifting larger elements to the right. The condition arr[j] > key ensures that all larger elements are moved rightward until key can be placed in the correct position.

• printArray function: This utility function prints the contents of the array.

• main function: This function defines an array of integers, prints it before sorting, calls the insertionSort function to sort the array, and then prints the sorted array.

Time Complexity of Insertion Sort

Worst Case: \(O(n^2)\)

In the worst case, the array is sorted in reverse order. For each element, we need to shift all previously sorted elements. This results in a time complexity of \(O(n^2)\), where there are \(n-1\) passes and, on average, each pass requires shifting \(n/2\) elements.

Best Case: \(O(n)\)

In the best case, the array is already sorted. The inner loop doesn't need to make any shifts, and each pass inserts the element in its current position, resulting in a time complexity of \(O(n)\).

Average Case: \(O(n^2)\)

In general, the average case requires shifting half of the elements in the sorted portion on each pass, leading to a time complexity of \(O(n^2)\).

Selection Sort

Selection Sort is a simple comparison-based sorting algorithm that divides the array into two parts: a sorted part and an unsorted part. It repeatedly selects the smallest (or largest) element from the unsorted part and swaps it with the leftmost unsorted element, gradually growing the sorted portion of the array.

Strategy of Selection Sort

Selection Sort works by finding the minimum element from the unsorted portion of the array and swapping it with the element at the current position. It does this for every position in the array, moving the boundary of the sorted and unsorted parts one element to the right after each pass.

Steps:

1. Start with the first element as the boundary between the sorted and unsorted parts.

2. Find the smallest element in the unsorted part.

3. Swap the smallest element with the first element of the unsorted part.

4. Move the boundary one element to the right and repeat the process until the array is sorted.

Inner Loop Behavior

The inner loop of Selection Sort iterates through the unsorted part of the array to find the smallest element. Unlike algorithms like Insertion Sort, the inner loop does not perform any shifting of elements but merely looks for the minimum. Once the minimum is found, it swaps with the first element of the unsorted part. This means that Selection Sort performs fewer swaps than some other sorting algorithms (like Bubble Sort), but the number of comparisons remains significant.

Example of Selection Sort

Let’s consider an array: [64, 25, 12, 22, 11].

Initial State:

[64, 25, 12, 22, 11]

Pass 1 (Find and Swap the Minimum):

• Unsorted part: [64, 25, 12, 22, 11]

• Find the minimum element (11)

• Swap 11 with 64

[11, 25, 12, 22, 64]

Pass 2 (Find and Swap the Minimum):

• Unsorted part: [25, 12, 22, 64]

• Find the minimum element (12)

• Swap 12 with 25

[11, 12, 25, 22, 64]

Pass 3 (Find and Swap the Minimum):

• Unsorted part: [25, 22, 64]

• Find the minimum element (22)

• Swap 22 with 25

[11, 12, 22, 25, 64]

Pass 4 (Find and Swap the Minimum):

• Unsorted part: [25, 64]

• Find the minimum element (25)

• No swap needed

[11, 12, 22, 25, 64]

At this point, the array is already sorted.

Final sorted array:

[11, 12, 22, 25, 64]

C Code for Selection Sort

#include <stdio.h>

// Function to perform Selection Sort
void selectionSort(int arr[], int n) {
    int i, j, min_idx;

    // Move boundary of the unsorted array
    for (i = 0; i < n-1; i++) {
        // Find the minimum element in the unsorted array
        min_idx = i;
        for (j = i+1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }

        // Swap the found minimum element with the first element
        if (min_idx != i) {
            int temp = arr[min_idx];
            arr[min_idx] = arr[i];
            arr[i] = temp;
        }
    }
}

// Function to print the array
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr)/sizeof(arr[0]);

    printf("Unsorted array: \n");
    printArray(arr, n);

    selectionSort(arr, n);

    printf("Sorted array: \n");
    printArray(arr, n);

    return 0;
}

Explanation of the C Code

• selectionSort function: This function implements the Selection Sort algorithm.

  • The outer loop iterates through the array, treating each element as the boundary between the sorted and unsorted portions.

  • The inner loop finds the minimum element in the unsorted portion by comparing each element with the current minimum (min_idx).

  • Once the minimum is found, it swaps it with the first element of the unsorted part. The min_idx != i condition checks whether a swap is necessary.

• printArray function: This utility function prints the contents of the array.

• main function: This function defines an array, prints it before sorting, calls the selectionSort function to sort the array, and then prints the sorted array.

Time Complexity of Selection Sort

Worst Case: \(O(n^2)\)

The outer loop runs \(n-1\) times, and for each pass, the inner loop runs \(n-i-1\) times to find the minimum element. This results in a total of \(O(n^2)\) comparisons. Since the algorithm makes the same number of comparisons regardless of the initial order of elements, the worst-case time complexity is \(O(n^2)\).

Best Case: \(O(n^2)\)

Even if the array is already sorted, Selection Sort will still make all the comparisons in each pass to find the minimum element. Therefore, the best-case time complexity is also \(O(n^2)\).

Average Case: \(O(n^2)\)

On average, Selection Sort performs the same number of comparisons in every case, so its time complexity remains \(O(n^2)\) for the average case as well.

Space Complexity: \(O(1)\)

Selection Sort is an in-place sorting algorithm, meaning it does not require any extra space other than a few variables for tracking the minimum index and swapping. Therefore, its space complexity is \(O(1)\).

Special Characteristics of Selection Sort

1. Number of Swaps: Selection Sort performs at most \(n-1\) swaps because it only swaps the current element with the smallest unsorted element once per pass. This makes it more efficient in terms of swaps compared to algorithms like Bubble Sort.

2. Unstable Sort: Selection Sort is not a stable sorting algorithm because it may change the relative order of equal elements.

Quick Sort

Quick Sort is a highly efficient, comparison-based, divide-and-conquer sorting algorithm. It works by selecting a "pivot" element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively or iteratively. This process of partitioning and sorting continues until the entire array is sorted.

Strategy of Quick Sort

Quick Sort uses a divide-and-conquer approach:

1. Divide: Select a pivot element and partition the array into two sub-arrays: one containing elements less than the pivot and the other containing elements greater than or equal to the pivot.

2. Conquer: Recursively or iteratively apply the same process to the two sub-arrays.

3. Combine: The sub-arrays are already sorted, so no additional work is needed to combine them.

Pivot in Quick Sort

The pivot is the key element around which the array is partitioned. It serves as the dividing point: elements smaller than the pivot go to the left, and elements larger than or equal to the pivot go to the right. The efficiency of Quick Sort heavily depends on the choice of the pivot.

How to Choose a Suitable Pivot?

Choosing a good pivot is crucial for Quick Sort's efficiency:

• First or Last Element: Simple to implement but can result in poor performance (\(O(n^2)\)) if the array is already sorted.

• Random Element: Picking a random element as the pivot can help mitigate the worst-case behavior.

• Median-of-Three: The pivot is chosen as the median of the first, middle, and last elements. This strategy provides better performance on average.

• Middle Element: The middle element is often a reasonable choice, particularly in practical implementations, to avoid poor performance on sorted arrays.

Iterative vs Recursive Quick Sort

Quick Sort is naturally implemented using recursion, but it can also be implemented iteratively using a stack to simulate the recursive behavior.

Recursive Quick Sort

Recursion simplifies the implementation by naturally handling the divide-and-conquer structure. After partitioning, Quick Sort is applied recursively to the two halves of the array.

Iterative Quick Sort

In the iterative version, a stack is used to store the indices of sub-arrays that need to be sorted. We simulate recursion by manually pushing the left and right sub-array indices onto the stack.

Example of Quick Sort

Let’s consider an array: [10, 80, 30, 90, 40, 50, 70].

Initial State:

[10, 80, 30, 90, 40, 50, 70]

We choose 50 as the pivot (middle element).

Partitioning Step 1:

Pivot = 50
Swap elements such that all smaller elements are to the left of the pivot and larger elements are to the right:
[10, 30, 40, 50, 90, 80, 70]

Now the array is split into two parts around the pivot 50:

• Left part: [10, 30, 40]

• Right part: [90, 80, 70]

Recursive Calls:

Left Partition:

Left part = [10, 30, 40]
Pivot = 30
Result after partitioning: [10, 30, 40]

Right Partition:

Right part = [90, 80, 70]
Pivot = 80
Result after partitioning: [70, 80, 90]

The final sorted array is:

[10, 30, 40, 50, 70, 80, 90]

C Code for Quick Sort

#include <stdio.h>

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

// Partition function that takes the last element as pivot, places
// the pivot at its correct position, and places all smaller elements
// to the left and greater elements to the right of the pivot.
int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // Pivot element is chosen as the last element
    int i = (low - 1);  // Index of smaller element

    for (int j = low; j <= high - 1; j++) {
        if (arr[j] < pivot) {
            i++;  // Increment index of smaller element
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i + 1);
}

// Recursive QuickSort function
void quickSort(int arr[], int low, int high) {
    if (low < high) {
        // Partition the array and get the pivot index
        int pi = partition(arr, low, high);

        // Recursively sort the sub-arrays before and after partition
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

// Function to print the array
void printArray(int arr[], int size) {
    for (int i = 0; i < size; 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("Unsorted array: \n");
    printArray(arr, n);

    quickSort(arr, 0, n - 1);

    printf("Sorted array: \n");
    printArray(arr, n);

    return 0;
}

Explanation of the C Code

• swap function: A utility function to swap two elements.

• partition function: This is the key function in Quick Sort. It selects the last element as the pivot, then rearranges the elements such that smaller elements are placed to the left of the pivot and larger elements to the right. The pivot element is placed in its correct sorted position.

• quickSort function: The recursive Quick Sort function. It first partitions the array using partition, then recursively sorts the left and right sub-arrays.

• printArray function: A utility function to print the contents of the array.

Time Complexity of Quick Sort

Worst Case: \(O(n^2)\)

The worst-case scenario for Quick Sort occurs when the pivot is consistently the smallest or largest element, such as when the array is already sorted in increasing or decreasing order. In this case, the partitioning only divides the array into one very small sub-array and one large sub-array, leading to \(O(n^2)\) time complexity.

Best Case: \(O(n \log n)\)

The best case occurs when the pivot consistently divides the array into two nearly equal sub-arrays, such as when the pivot is the median element. This results in a balanced recursion tree with a height of \(O(\log n)\), and each level of the recursion involves \(O(n)\) comparisons. Thus, the overall time complexity is \(O(n \log n)\).

Average Case: \(O(n \log n)\)

On average, Quick Sort performs well because the pivots usually divide the array into reasonably sized sub-arrays. The average case time complexity is \(O(n \log n)\), which makes Quick Sort highly efficient for most real-world datasets.

Space Complexity: \(O(\log n)\)

For the recursive version of Quick Sort, the space complexity comes from the recursive call stack. In the best and average cases, the recursion depth is \(O(\log n)\). However, in the worst case (when the array is already sorted), the recursion depth can be \(O(n)\), making the space complexity \(O(n)\) in the worst case.

Merge Sort

Merge Sort is a stable, comparison-based, divide-and-conquer sorting algorithm. It works by recursively dividing the array into two halves, sorting each half, and then merging the two sorted halves back together. The main idea behind Merge Sort is to break the problem down into smaller subproblems (sorting smaller arrays), which are easier to solve, and then combine the results to solve the original problem.

Strategy of Merge Sort

Merge Sort uses the divide-and-conquer approach:

1. Divide: Recursively split the array into two halves until each sub-array has only one element (since a single element is trivially sorted).

2. Conquer: Recursively sort the two sub-arrays.

3. Combine: Merge the two sorted sub-arrays back into a single sorted array.

The merge operation is where most of the work happens in Merge Sort. During the merge process, two sorted arrays are combined into one sorted array.

Steps of Merge Sort:

1. Divide the array into two halves.

2. Recursively sort each half.

3. Merge the two halves by comparing the smallest elements of each half and placing the smaller element into the result array, repeating this until both halves are merged.

Example of Merge Sort

Let’s consider an array: [38, 27, 43, 3, 9, 82, 10].

Initial State:

[38, 27, 43, 3, 9, 82, 10]

Step 1: Divide the array

[38, 27, 43, 3]      [9, 82, 10]

Step 2: Divide further

[38, 27]   [43, 3]      [9, 82]   [10]

Step 3: Continue dividing

[38] [27]   [43] [3]      [9] [82]   [10]

Step 4: Start merging sorted sub-arrays

[27, 38]   [3, 43]      [9, 82]   [10]

Step 5: Continue merging

[3, 27, 38, 43]   [9, 10, 82]

Step 6: Final merge

[3, 9, 10, 27, 38, 43, 82]

Final sorted array:

[3, 9, 10, 27, 38, 43, 82]

C Code for Merge Sort

#include <stdio.h>

// Merge function to combine two sorted halves into a single sorted array
void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1; // Size of left sub-array
    int n2 = r - m;     // Size of right sub-array

    // Temporary arrays to hold left and right sub-arrays
    int L[n1], R[n2];

    // Copy data to temporary arrays L[] and R[]
    for (int i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (int j = 0; j < n2; j++)
        R[j] = arr[m + 1 + j];

    // Initial indexes for sub-arrays and the merged array
    int i = 0, j = 0, k = l;

    // Merge the two sub-arrays back into arr[]
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    // Copy any remaining elements of L[], if any
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }

    // Copy any remaining elements of R[], if any
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

// Recursive function to divide the array and call merge
void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        // Find the middle point
        int m = l + (r - l) / 2;

        // Recursively sort the first and second halves
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);

        // Merge the sorted halves
        merge(arr, l, m, r);
    }
}

// Function to print the array
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// Main function to test the Merge Sort algorithm
int main() {
    int arr[] = {38, 27, 43, 3, 9, 82, 10};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Unsorted array: \n");
    printArray(arr, n);

    mergeSort(arr, 0, n - 1);

    printf("Sorted array: \n");
    printArray(arr, n);

    return 0;
}

Explanation of the C Code

• merge function: This function takes the two halves of the array (each sorted), and merges them back into the original array in sorted order. It uses two temporary arrays (L[] for the left half and R[] for the right half) to store the values of the sub-arrays, and then merges them back into the main array.

• mergeSort function: This recursive function splits the array into two halves until it reaches the base case (an array with one element, which is already sorted). Once the array is split, it calls the merge function to combine the two sorted halves back together.

• printArray function: This utility function prints the elements of the array.

• main function: The main function defines an unsorted array, prints it, sorts it using mergeSort, and prints the sorted array.

Time Complexity of Merge Sort

Worst Case: \(O(n \log n)\)

In Merge Sort, the array is recursively divided into two halves, creating a binary tree structure. The height of this tree is \(O(\log n)\) because we are dividing the array in half at each level. At each level of recursion, we merge all elements back together, which takes \(O(n)\) time. Therefore, the overall time complexity is \(O(n \log n)\).

Best Case: \(O(n \log n)\)

Even if the array is already sorted, Merge Sort will still divide and merge the sub-arrays in the same manner. Thus, the best-case time complexity is also \(O(n \log n)\).

Average Case: \(O(n \log n)\)

On average, Merge Sort divides the array into two halves and merges them in \(O(n \log n)\) time, making it highly efficient for a wide range of inputs.

Space Complexity: \(O(n)\)

Merge Sort uses extra space to store temporary arrays for merging the two halves. These temporary arrays require additional memory of size \(n\), where \(n\) is the size of the input array. Thus, the space complexity is \(O(n)\).

Special Characteristics of Merge Sort

1. Stable Sort: Merge Sort is stable, meaning that it preserves the relative order of equal elements.

2. Not In-Place: Merge Sort requires additional space for the temporary arrays used during the merging process, which makes it less space-efficient than in-place algorithms like Quick Sort.

3. Guaranteed \(O(n \log n)\) Performance: Unlike Quick Sort, Merge Sort's time complexity is always \(O(n \log n)\), even in the worst case.

Radix Sort

Radix Sort is a non-comparison-based sorting algorithm that works by sorting the elements digit by digit, starting from the least significant digit (LSD) to the most significant digit (MSD). It is particularly useful for sorting integers and can be adapted to sort strings or floating-point numbers. Unlike comparison-based algorithms, Radix Sort uses counting or bucket sorting as a subroutine to distribute elements into groups according to their digits.

Radix Sort is highly efficient for sorting numbers with a fixed number of digits, and its time complexity can be lower than comparison-based algorithms like Quick Sort and Merge Sort for specific data types.

Strategy of Radix Sort

Radix Sort processes each digit of the numbers being sorted, starting from the least significant digit (LSD) and moving towards the most significant digit (MSD). It applies a stable sorting algorithm, such as Counting Sort, to sort the array based on each digit.

Steps of Radix Sort:

1. Find the maximum number in the array to determine the number of digits.

2. Sort the array by each digit: Start from the least significant digit (rightmost), apply a stable sort (e.g., Counting Sort), and then move to the next significant digit.

3. Repeat the process for all digits until the most significant digit is sorted.

Example of Radix Sort

Let’s consider an array: [170, 45, 75, 90, 802, 24, 2, 66].

Step 1: Sort by the least significant digit (1s place)

Original Array:    [170, 45, 75, 90, 802, 24, 2, 66]
Sort by 1s digit:  [170, 90, 802, 2, 24, 45, 75, 66]

Step 2: Sort by the 10s digit

Array after 1st pass:  [170, 90, 802, 2, 24, 45, 75, 66]
Sort by 10s digit:     [802, 2, 24, 45, 66, 75, 170, 90]

Step 3: Sort by the 100s digit

Array after 2nd pass:  [802, 2, 24, 45, 66, 75, 170, 90]
Sort by 100s digit:    [2, 24, 45, 66, 75, 90, 170, 802]

Final sorted array:

[2, 24, 45, 66, 75, 90, 170, 802]

C Code for Radix Sort

#include <stdio.h>

// A function to get the maximum value in arr[]
int getMax(int arr[], int n) {
    int max = arr[0];
    for (int i = 1; i < n; i++)
        if (arr[i] > max)
            max = arr[i];
    return max;
}

// A function to do counting sort based on the digit represented by exp (10^exp)
void countingSort(int arr[], int n, int exp) {
    int output[n];  // Output array
    int count[10] = {0};  // Count array for digits 0-9

    // Store the count of occurrences of each digit
    for (int i = 0; i < n; i++)
        count[(arr[i] / exp) % 10]++;

    // Change count[i] so that it contains the actual position of this digit in the output array
    for (int i = 1; i < 10; i++)
        count[i] += count[i - 1];

    // Build the output array
    for (int i = n - 1; i >= 0; i--) {
        output[count[(arr[i] / exp) % 10] - 1] = arr[i];
        count[(arr[i] / exp) % 10]--;
    }

    // Copy the output array to arr[], so that arr[] now contains sorted numbers according to the current digit
    for (int i = 0; i < n; i++)
        arr[i] = output[i];
}

// Main function to implement radix sort
void radixSort(int arr[], int n) {
    // Find the maximum number to know the number of digits
    int max = getMax(arr, n);

    // Do counting sort for every digit. exp is 10^i where i is the current digit position (1s, 10s, 100s, etc.)
    for (int exp = 1; max / exp > 0; exp *= 10)
        countingSort(arr, n, exp);
}

// A utility function to print an array
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

// Main function to test the radix sort algorithm
int main() {
    int arr[] = {170, 45, 75, 90, 802, 24, 2, 66};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Unsorted array: \n");
    printArray(arr, n);

    radixSort(arr, n);

    printf("Sorted array: \n");
    printArray(arr, n);

    return 0;
}

Explanation of the C Code

• getMax function: This function finds the maximum number in the array. Knowing the maximum number helps determine how many digits we need to process in Radix Sort.

• countingSort function: This is a modified Counting Sort that sorts the array based on a specific digit. The parameter exp represents the current digit's place (1 for ones, 10 for tens, etc.). The function uses a count array to store the frequency of each digit and then builds the output array by placing elements in the correct positions based on their current digit.

• radixSort function: The main function that implements Radix Sort. It first finds the maximum number to determine the number of digits, then repeatedly calls countingSort for each digit (starting with the least significant digit and moving to the most significant).

• printArray function: This utility function prints the contents of the array.

• main function: The main function defines an unsorted array, prints it, sorts it using Radix Sort, and prints the sorted array.

Time Complexity of Radix Sort

Worst Case: \(O(d \cdot (n + k))\)

• n: Number of elements in the array.

• d: Number of digits in the largest number.

• k: Range of digits, which is 10 in the case of base-10 numbers.

The worst-case time complexity of Radix Sort is determined by the number of digits (\(d\)) and the time taken by Counting Sort (\(O(n + k)\)) for each digit. Since \(k\) is constant (for base 10, \(k = 10\)), the time complexity simplifies to \(O(d \cdot n)\).

Best Case: \(O(d \cdot n)\)

In the best case, Radix Sort performs \(O(d \cdot n)\) operations since it processes each digit of each number exactly once.

Average Case: \(O(d \cdot n)\)

On average, Radix Sort performs \(O(d \cdot n)\) operations because it always processes each digit for every number.

Space Complexity: \(O(n + k)\)

Radix Sort requires additional space for the output array and the count array. Since \(k\) is constant (10 for base-10 numbers), the space complexity is \(O(n + k)\), which simplifies to \(O(n)\) for large inputs.

Special Characteristics of Radix Sort

1. Non-Comparison Based: Radix Sort doesn't compare elements directly like Quick Sort or Merge Sort, making it highly efficient for specific types of data, such as fixed-length integers.

2. Stable Sort: Radix Sort is stable, meaning that it preserves the relative order of equal elements. This is particularly important when sorting multi-field records.

3. Efficient for Large Data: Radix Sort can be more efficient than comparison-based algorithms (like Quick Sort) for large datasets with a fixed number of digits.

4. Not In-Place: Radix Sort requires extra space for storing the temporary output array, making it less space-efficient than some other in-place algorithms.