Code: Merge Sort | Basics of C++ - Software Development PDF Download

Introduction

Merge sort is a popular and efficient sorting algorithm that falls under the category of divide and conquer algorithms. It is often considered one of the best sorting algorithms due to its stability, predictable performance, and relatively simple implementation. In this article, we will explore how to implement the merge sort algorithm in C++.

Understanding the Merge Sort Algorithm

The merge sort algorithm follows a divide and conquer approach, which means it breaks down the problem into smaller subproblems until they become simple enough to solve. The basic steps of the merge sort algorithm are as follows:

• Divide: The unsorted array is divided into two halves.
• Conquer: Each half is recursively sorted using the merge sort algorithm.
• Combine: The two sorted halves are merged to produce a single sorted array.

Implementation of Merge Sort in C++

Let's now look at the C++ implementation of the merge sort algorithm. We will start by defining a function 'mergeSort()' that takes an array, its leftmost index, and its rightmost index as parameters.

#include <iostream>

using namespace std;

void merge(int arr[], int left, int middle, int right) {

    int i, j, k;

    int n1 = middle - left + 1;

    int n2 = right - middle;

    // Create temporary arrays

    int L[n1], R[n2];

    // Copy data to temporary arrays

    for (i = 0; i < n1; i++)

        L[i] = arr[left + i];

    for (j = 0; j < n2; j++)

        R[j] = arr[middle + 1 + j];

    // Merge the temporary arrays back into arr[l..r]

    i = 0;

    j = 0;

    k = left;

    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++;

    }

}

void mergeSort(int arr[], int left, int right) {

    if (left < right) {

        // Find the middle point

        int middle = left + (right - left) / 2;

        // Sort first and second halves

        mergeSort(arr, left, middle);

        mergeSort(arr, middle + 1, right);

        // Merge the sorted halves

        merge(arr, left, middle, right);

    }

}

int main() {

    int arr[] = { 12, 11, 13, 5, 6, 7 };

    int arrSize = sizeof(arr) / sizeof(arr[0]);

    cout << "Original array: ";

    for (int i = 0; i < arrSize; i++)

        cout << arr[i] << " ";

    cout << endl;

    mergeSort(arr, 0, arrSize - 1);

    cout << "Sorted array: ";

    for (int i = 0; i < arrSize; i++)

        cout << arr[i] << " ";

    cout << endl;

    return 0;

}

In this code snippet, we first define the 'merge()' function, which is responsible for merging two sorted subarrays into one. Then, we define the 'mergeSort()' function, which recursively divides the array into smaller subarrays and performs the merge operation.

Explanation of the Code

• The merge() function takes four parameters: the array arr[], the leftmost index of the subarray left, the middle index of the subarray middle, and the rightmost index of the subarray right.
• Inside the merge() function, we create two temporary arrays, L[] and R[], to store the elements of the two subarrays.
• The elements from the original array are then copied to the temporary arrays.
• Next, we merge the elements from the temporary arrays back into the original array by comparing the elements and placing them in the correct order.
• After merging, any remaining elements from the temporary arrays are copied back into the original array.
• The mergeSort() function takes three parameters: the array arr[], the leftmost index of the subarray left, and the rightmost index of the subarray right.
• The mergeSort() function implements the divide and conquer strategy by recursively calling itself to sort the subarrays.
• Finally, in the main() function, we initialize an array and call the mergeSort() function to sort the array. The sorted array is then printed.

Code Output

Running the above code will produce the following output:

Original array: 12 11 13 5 6 7

Sorted array: 5 6 7 11 12 13

Sample Problems

Problem: Sort the following array using merge sort: '{ 7, 2, 9, 1, 6, 5 }'. Output the sorted array.

After applying merge sort, the sorted array will be: '{ 1, 2, 5, 6, 7, 9 }'.

Problem: Sort the following array in descending order using merge sort: { 3, 8, 1, 4, 6, 2 }. Output the sorted array.

By modifying the comparison condition in the merge() function to L[i] >= R[j], the sorted array in descending order will be: { 8, 6, 4, 3, 2, 1 }.

Problem: What is the time complexity of the merge sort algorithm?

The time complexity of merge sort is O(n log n), where n is the number of elements in the array. This makes it an efficient sorting algorithm for large datasets.

Conclusion

In this article, we explored the merge sort algorithm and its implementation in C++. We learned how merge sort follows a divide and conquer approach to efficiently sort an array. By understanding the code and examples provided, you should now have a solid foundation in implementing merge sort in C++.