C Program: Merge Sort in Descending Order

1. Introduction

Merge Sort is an efficient, comparison-based, divide-and-conquer sorting algorithm. By repeatedly dividing the unsorted list into halves until each sublist contains just one element and then merging these sublists in the right order, we can achieve a sorted list. For descending order, the merging process is slightly adjusted so that higher values are placed before lower ones.

2. Program Overview

The program comprises:

1. merge: A function to merge two halves of an array in descending order.

2. mergeSort: The main function that sorts the array using the Merge Sort algorithm.

3. printArray: A utility function to display the contents of the array.

4. main: The starting point of program execution.

3. Code Program

#include <stdio.h>
#include <stdlib.h>

// Merges two subarrays of arr[] in descending order.
void merge(int arr[], int l, int m, int r) {
    int i, j, k;
    int n1 = m - l + 1;
    int n2 = r - m;

    // Create temp arrays
    int L[n1], R[n2];

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

    // Merge the temp arrays back into arr[l..r] in descending order
    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2) {
        if (L[i] >= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

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

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

// Main function that sorts arr[l..r] using merge()
void mergeSort(int arr[], int l, int r) {
    if (l < r) {
        // Find the middle point
        int m = l + (r - l) / 2;

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

        merge(arr, l, m, r);
    }
}

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

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

    printf("Given array is \n");
    printArray(arr, arr_size);

    mergeSort(arr, 0, arr_size - 1);

    printf("Sorted array in descending order is \n");
    printArray(arr, arr_size);
    return 0;
}

Output:

Given array is
38 27 43 3 9 82 10
Sorted array in descending order is
82 43 38 27 10 9 3

4. Step By Step Explanation

1. The mergeSort function recursively divides the array into two halves until each sub-array has a single element.

2. The merge function takes two sorted sub-arrays as inputs and merges them in descending order. It does this by checking the largest values first from the sub-arrays and placing them at the beginning of the merged array.

3. Once both halves of the array are sorted in descending order, they are merged back together to result in a fully sorted array in descending order.

4. The process of division and merging continues recursively, ensuring that each merged sub-array is sorted in descending order.

Merge Sort's beauty lies in its efficiency and stability, making it a preferred algorithm for many computational tasks involving sorting.

Related C Programs on Sorting Algorithms

1. Bubble Sort in Ascending Order in C
2. Bubble Sort in Descending Order in C
3. Selection Sort in Ascending Order in C
4. Selection Sort in Descending Order in C
5. Insertion Sort in Ascending Order in C
6. Insertion Sort in Descending Order in C
7. Merge Sort in Ascending Order in C
8. Merge Sort in Descending Order in C
9. Quick Sort in Ascending Order in C
10. Quick Sort in Descending Order in C
11. Heap Sort in Ascending Order in C
12. Heap Sort in Descending Order in C