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. The array is repeatedly divided into two halves until each range contains only one element, which is already sorted.
The sorted ranges are then merged by comparing their current values and placing the smaller value first. Equal values are taken from the left range to preserve stability.
Each merge builds a larger sorted range, and this process continues until the complete array becomes sorted.
Algorithm
Begin with the full range from index
0to indexn - 1so every array position participates in sorting.Stop a recursive call when
left >= rightbecause a range containing at most one value is already sorted.Calculate the middle index with
left + (right - left) / 2so two balanced smaller ranges are formed without adding both boundaries directly.Sort the left and right ranges recursively so both ranges satisfy the ordered-input requirement of the merge operation.
Keep two range pointers and a temporary array so comparisons preserve every unmerged value from both sorted ranges.
Compare both current values and take the left value on equality because the smallest available value belongs next and left-first equality preserves stability.
Copy remaining values and write the temporary array back into the current range so the parent call receives one completely sorted range.
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.