Algorithm Deep Dive CPP Implementation

Implementation of Merge Sort in CPP Programming Language

5 min read

Merge Sort is one of the most efficient and widely used sorting algorithms. It follows the divide-and-conquer approach, which means it breaks down a problem into smaller subproblems, solves them, and then combines the results. Merge Sort is particularly useful because it guarantees a time complexity of O(n log n) in all cases, making it a reliable choice for sorting large datasets.

In this article, we will briefly touch upon how Merge Sort works, go through its implementation in C++ and understand the implementation.

How Merge Sort Works

Merge Sort works by recursively dividing the input array into smaller subarrays until each subarray contains only one element. Then, it keeps merging these subarrays in a sorted order. Here’s a step-by-step breakdown:

  1. Divide: Split the array into two halves.
  2. Conquer: Recursively sort each half.
  3. Combine: Merge the two sorted halves into a single sorted array.

Refer to these articles for better understanding on how merge sort algorithm works:

Implementation of Merge Sort Algorithm in C++

Here’s the implementation of Merge Sort Algorithm in C++:

Loading code…

Explanation of the Implementation

Let’s break down the merge sort implementation step by step to understand how it works.

The mergeSort Method

The mergeSort method is the main method that performs the sorting. It takes three parameters:

  1. arr: Reference to the vector to be sorted.
  2. left: The starting index of the segment of the vector to be sorted.
  3. right: The ending index of the segment of the vector to be sorted.

Here’s how it works:

  1. Base Condition: The method first checks if left < right. This condition ensures that the array has more than one element. If left is not less than right, it means the array has either one or zero elements, and no sorting is needed.
  2. Divide the Array: If the array has more than one element, the method calculates the middle index (mid) using the formula left + (right - left) / 2. This divides the array into two halves and avoids potential integer overflow.
  3. Recursive Calls: The method then calls itself recursively to sort the left half (mergeSort(arr, left, mid)) and the right half (mergeSort(arr, mid + 1, right)). This process continues until the array is divided into single-element subarrays.
  4. Merge the Sorted Halves: Once the two halves are sorted, the merge method is called to merge them back into a single sorted array.

The merge Method

The merge method is responsible for merging two sorted subarrays into a single sorted array. It takes four parameters:

  1. arr: Reference to the vector containing the two subarrays to be merged.
  2. left: The starting index of the first subarray.
  3. mid: The ending index of the first subarray.
  4. right: The ending index of the second subarray.

Here’s how it works:

  1. Calculate Subarray Sizes: The sizes of the two subarrays are calculated using n1 = mid - left + 1 (size of the left subarray) and n2 = right - mid (size of the right subarray).

  2. Create Temporary Vectors: Two temporary vectors, L and R, are created to hold the elements of the left and right subarrays. The elements are copied from the main array to these temporary vectors.

  3. Merge Process: The method then merges the two subarrays back into the main array (arr). It uses three indices:

    • i: Index for the left subarray (L).
    • j: Index for the right subarray (R).
    • k: Index for the main array (arr).

    The method compares the elements of L and R one by one. The smaller element is placed into the main array, and the corresponding index (i or j) is incremented. This process continues until all elements from either L or R are placed into the main array.

  4. Copy Remaining Elements: If there are any remaining elements in L or R, they are copied directly into the main array.

Example Run

Let’s walk through an example with the vector [4, 1, 2, 3]:

  1. The mergeSort method is called with left = 0 and right = 3.
  2. The array is divided into two halves: [4, 1] and [2, 3].
  3. Each half is further divided and sorted recursively:
    • [4, 1] becomes [4] and [1], which are merged into [1, 4].
    • [2, 3] becomes [2] and [3], which are merged into [2, 3].
  4. Finally, the two sorted halves [1, 4] and [2, 3] are merged into the final sorted array [1, 2, 3, 4].

Implementation in other Languages