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
0ton - 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) / 2to 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,
leftPartandrightPart, 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
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 codeint 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.
Be the first to add a comment.