1. Introduction

In this blog post, we will learn how to write a C++ program to sort an array of integers in Descending Order using the Merge Sort algorithm.

Merge Sort is a 'divide and conquer' algorithm. The basic idea is to split the array into two halves, recursively sort each half, and then merge the sorted halves. This blog post demonstrates how to implement Merge Sort in C++ for sorting an array in descending order.

2. Program Overview

1. merge(): Function to merge two halves of an array.

2. mergeSort(): The recursive function that divides the array and sorts them.

3. printArray(): Utility function to display the array's elements.

4. main(): The main function that starts the program.

3. Code Program

#include<iostream>
using namespace std;

// Merges two subarrays of arr[]
void merge(int arr[], int l, int m, int r) {
    int n1 = m - l + 1;
    int n2 = r - m;

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

    // Copy data to temp 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];

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

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

    // Copy the remaining elements of R[], if 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) return; // Base case
    int m = l + (r - l) / 2; // Calculate mid point of array
    mergeSort(arr, l, m); // Sort first half
    mergeSort(arr, m + 1, r); // Sort second half
    merge(arr, l, m, r); // Merge the sorted halves
}

// Utility function to print the array
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
    cout << endl;
}

// Driver code
int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int arr_size = sizeof(arr) / sizeof(arr[0]);
    
    cout << "Original array is: \n";
    printArray(arr, arr_size);
    
    mergeSort(arr, 0, arr_size - 1);
    
    cout << "Sorted array in descending order is: \n";
    printArray(arr, arr_size);
    return 0;
}

Output:

Original array is:
12 11 13 5 6 7 
Sorted array in descending order is: 
13 12 11 7 6 5

4. Step By Step Explanation

1. merge(): This function is tasked with merging two halves of an array. Temporary arrays L and R are created to hold the two halves. We've modified the merge logic to compare elements in a way that sorts them in descending order.

2. mergeSort(): This is the recursive function that repeatedly splits the array in half, sorts each half, and then merges them back together.

3. printArray(): This is a utility function that prints the elements of the array. It provides a visualization of the array before and after sorting.

4. main(): This function sets up a sample array, displays its elements, calls the mergeSort function to sort the array, and finally displays the sorted elements.

The primary modification for descending order was in the merge() function where the condition to compare elements of L and R was changed to L[i] >= R[j].

Related C++ Programs on Sorting Algorithms

Related C++ Programs with Output and Step-By-Step Explanation:

Java Guides

Search This Blog

Merge Sort in Descending Order in C++