Merge Sort | DSA in C++ - Software Development PDF Download

Introduction

Sorting is an essential operation in computer science and plays a vital role in various applications. One of the most efficient sorting algorithms is Merge Sort. It is a divide-and-conquer algorithm that divides the input array into two halves, recursively sorts them, and then merges the two sorted halves to produce a sorted output.

In this article, we will explore Merge Sort in detail, including its working principle, implementation in C++, and examples to illustrate its functionality.

Working Principle

Merge Sort follows a simple principle:

• Divide the unsorted array into two halves.
• Recursively sort the two halves.
• Merge the sorted halves to obtain the final sorted array.

The algorithm uses a helper function, 'merge()', to merge the two sorted subarrays.

Merge Sort Implementation in C++

Let's dive into the implementation of Merge Sort in C++:

#include <iostream>

using namespace std;

// Merge two sorted subarrays into a single sorted array

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

    int i = 0, j = 0, k = 0;

    while (i < leftSize && j < rightSize) {

        if (left[i] <= right[j]) {

            arr[k] = left[i];

            i++;

        } else {

            arr[k] = right[j];

            j++;

        }

        k++;

    }

    // Copy remaining elements from left array (if any)

    while (i < leftSize) {

        arr[k] = left[i];

        i++;

        k++;

    }

    // Copy remaining elements from right array (if any)

    while (j < rightSize) {

        arr[k] = right[j];

        j++;

        k++;

    }

}

// Merge Sort implementation

void mergeSort(int arr[], int size) {

    if (size < 2) {

        return;  // Base case: an array with 0 or 1 element is already sorted

    }

    int mid = size / 2;

    // Create left and right subarrays

    int left[mid];

    int right[size - mid];

    // Populate left and right subarrays

    for (int i = 0; i < mid; i++) {

        left[i] = arr[i];

    }

    for (int i = mid; i < size; i++) {

        right[i - mid] = arr[i];

    }

    // Recursively sort left and right subarrays

    mergeSort(left, mid);

    mergeSort(right, size - mid);

    // Merge the sorted subarrays

    merge(arr, left, mid, right, size - mid);

}

// Utility function to print an 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[] = {7, 2, 1, 6, 8, 5, 3, 4};

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

    cout << "Original array: ";

    printArray(arr, size);

    mergeSort(arr, size);

    cout << "Sorted array: ";

    printArray(arr, size);

    return 0;

}

Explanation
Let's understand the implementation step by step:

• The 'merge()' function takes in five parameters: the original array ('arr'), the left subarray ('left'), the size of the left subarray ('leftSize'), the right subarray ('right'), and the size of the right subarray ('rightSize').
• Inside the merge() function, we compare the elements of the left and right subarrays one by one and store the smaller element in the original array ('arr'). We use three variables ('i', 'j', and 'k') to keep track of the indices of the left subarray, right subarray, and the original array, respectively.
• After the initial comparison, if there are any remaining elements in the left or right subarrays, we copy them into the original array.
• The 'mergeSort()' function takes in two parameters: the array to be sorted ('arr') and the size of the array ('size').
• The base case of the 'mergeSort()' function is when the array size is less than 2. In this case, the array is already sorted, so we return.
• If the base case is not satisfied, we calculate the middle index ('mid') of the array.
• We create two subarrays ('left' and 'right') to store the elements of the left and right halves of the original array.
• The elements are divided and stored accordingly in the left and right subarrays.
• Recursively, we call 'mergeSort()' on the left and right subarrays to sort them.
• Finally, we call the 'merge()' function to merge the sorted subarrays into the original array.

Example and Output
Let's consider an example and observe the output of the Merge Sort implementation:

Input:

Original array: 7 2 1 6 8 5 3 4

Output:

Sorted array: 1 2 3 4 5 6 7 8

Sample Problems

Here are a few sample problems related to Merge Sort that you can try to solve:

Problem 1: Given an array of integers, sort it in non-decreasing order using Merge Sort.

Input: [5, 1, 4, 2, 8]

Output: [1, 2, 4, 5, 8]

Problem 2: Given a list of names, sort them in alphabetical order using Merge Sort.

Input: ["Alice", "David", "Charlie", "Bob"]

Output: ["Alice", "Bob", "Charlie", "David"]

Problem 3: Given an array of strings, sort them in non-decreasing order based on their lengths using Merge Sort.

Input: ["apple", "banana", "cat", "dog"]

Output: ["cat", "dog", "apple", "banana"]

Conclusion

Merge Sort is an efficient sorting algorithm that divides the input array into two halves, recursively sorts them, and then merges the sorted halves to produce a sorted output. It follows the divide-and-conquer approach and has a time complexity of O(n log n), making it suitable for large datasets.
By understanding the working principle and implementation of Merge Sort, you can effectively sort arrays and solve various sorting problems.