Merge Sort Algorithm: Divide and Conquer Explained

377.2k
5

An integer array arr is given. Rearrange all values in non-decreasing order by applying the merge sort algorithm.

The array must be divided into smaller parts, sorted parts must be merged in order, and the final sorted array must be returned.

Example 1

Input: arr = [38, 27, 43, 10]
Output: [10, 27, 38, 43]
Explanation: The array is divided into [38, 27] and [43, 10]. Smaller parts become [27, 38] and [10, 43], then both sorted parts are merged into [10, 27, 38, 43].

Example 2

Input: arr = [5]
Output: [5]
Explanation: A single value already forms a sorted range, so no split or merge is required.

Approach

Merge sort follows the Divide-and-Conquer idea. Instead of trying to sort the entire array at once, it breaks the problem into smaller subproblems that are easier to solve. The idea is to divide the array into two halves repeatedly until each subarray contains exactly one element. A single-element array is already sorted because there is no other element with which it needs to be compared.

Once we reach these single-element arrays, we start combining them. We take two sorted subarrays at a time and merge them into a single sorted subarray.

To merge two sorted subarrays, compare their current unprocessed elements and place the smaller one into the resulting array. We continue this process until all elements from both subarrays have been placed. If one subarray becomes empty before the other, simply append the remaining elements of the non-empty subarray. Each merge combines two smaller sorted ranges into a larger sorted range. This process continues until all the smaller ranges are merged into one complete sorted array.

Algorithm

  • Start with the complete array, considering the range from index 0 to n - 1, so every element participates in sorting.

  • Check the base case left >= right. If true, the range contains at most one element and is already sorted, so return.

  • Calculate the middle index using left + (right - left) / 2 to divide the current range into two smaller, non-overlapping halves.

  • Recursively sort the left and right halves. Once both recursive calls return, both halves are individually sorted.

  • Copy the two sorted halves into separate temporary arrays, leftPart and rightPart, to preserve their values during merging.

  • Use two pointers to track the current elements in the temporary arrays and a third pointer to track the next position to fill in the original array.

  • Compare the current elements of both arrays and place the smaller one into the original array. If both are equal, take the left element first to maintain stability.

  • Once either temporary array becomes empty, copy the remaining elements of the other array directly, as they are already sorted.

  • Continue this process until all recursive calls finish, resulting in one completely sorted array.

Dry Run

Merge Sort Image

Merge Sort Image

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Merges two sorted ranges into the original array.
void merge(vector<int>& arr, int left, int mid, int right) {
vector<int> leftPart;
vector<int> rightPart;
// Copy left range to preserve values during merging.
for (int index = left; index <= mid; index++) {
leftPart.push_back(arr[index]);
}
// Copy right range for safe comparison during merging.
for (int index = mid + 1; index <= right; index++) {
rightPart.push_back(arr[index]);
}
int leftIndex = 0;
int rightIndex = 0;
int writeIndex = left;
// Compare both ranges until one becomes empty.
while (leftIndex < leftPart.size() && rightIndex < rightPart.size()) {
// Take from left on equality to keep sorting stable.
if (leftPart[leftIndex] <= rightPart[rightIndex]) {
arr[writeIndex] = leftPart[leftIndex];
leftIndex++;
} else {
arr[writeIndex] = rightPart[rightIndex];
rightIndex++;
}
writeIndex++;
}
// Copy remaining left values as they are already sorted.
while (leftIndex < leftPart.size()) {
arr[writeIndex] = leftPart[leftIndex];
leftIndex++;
writeIndex++;
}
// Copy remaining right values as they are already sorted.
while (rightIndex < rightPart.size()) {
arr[writeIndex] = rightPart[rightIndex];
rightIndex++;
writeIndex++;
}
}
// Divides the range and merges both sorted halves.
void mergeSortHelper(vector<int>& arr, int left, int right) {
// A range of zero or one value is already sorted.
if (left >= right) {
return;
}
int mid = left + (right - left) / 2;
// Sort left half before merging.
mergeSortHelper(arr, left, mid);
// Sort right half before merging.
mergeSortHelper(arr, mid + 1, right);
// Merge both sorted halves.
merge(arr, left, mid, right);
}
public:
// Sorts the array using merge sort.
vector<int> mergeSort(vector<int>& arr) {
int n = arr.size();
// Arrays with fewer than two values are already sorted.
if (n < 2) {
return arr;
}
mergeSortHelper(arr, 0, n - 1);
return arr;
}
};
// Driver code
int main() {
// Input array
vector<int> arr = {38, 27, 43, 10};
// Create solution object
Solution obj;
// Sort and print the result
vector<int> answer = obj.mergeSort(arr);
for (int value : answer) {
cout << value << " ";
}
cout << endl;
return 0;
}

Complexity Analysis

Time Complexity: O(N log N), because the array is split across log N levels and every level performs O(N) total merging work.

Space Complexity: O(N) auxiliary space for temporary merge arrays and O(log N) recursion stack space for balanced recursive calls.

Interview follow-up Questions

Yes. Stability is preserved when equal values are copied from the left sorted range before equal values from the right sorted range. Original order among equal values remains unchanged.

Sorting

Read Similar Blogs

Comments0