Merge Sorted Subarrays Editorial

Practice Problem Link: Merge Sorted Subarrays | Practice Problem

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Consider an array that is divided into two parts and both of the parts are sorted individually. Given the mentioned array and the end index of the first part, merge them to create a sorted array.

Naive Approach

This problem can be solved by just sorting the array.

Analysis

• Time Complexity: O(n * log(n))
• Auxiliary Space Complexity: O(1)

Implementation

C++

void merge(vector<int> &arr, int endIndex) {
    sort (arr.begin(),arr.end());
}

Java

class Solution {
    void merge (int[] arr, int endIndex) {
        Arrays.sort(arr);
    }
}

Optimal Approach

The problem can be solved by traversing both the arrays simultaneously and adding the current smaller element in a new array. Finally, if there are remaining elements in any array add them to the new array.

Analysis

• Time Complexity: O(n)
• Auxiliary Space Complexity: O(n)

Implementation

C++

void merge(vector<int> &arr, int endIndex) {
   int subarr1Current = 0, subarr2Current = endIndex + 1;
   vector<int> ans;
   while (subarr1Current <= endIndex && subarr2Current < arr.size()) {
       if(arr[subarr1Current] < arr[subarr2Current]) {
           ans.push_back(arr[subarr1Current++]);
       } else {
           ans.push_back(arr[subarr2Current++]);
       }
   }
   while (subarr1Current <= endIndex) {
       ans.push_back(arr[subarr1Current++]);
   }
   while (subarr2Current < arr.size()) {
       ans.push_back(arr[subarr2Current++]);
   }
   for (int i = 0; i < arr.size(); i++) {
       arr[i] = ans[i];
   }
}

Java

class Solution {
   void merge (int[] arr, int endIndex) {
       int subarr1Current = 0, subarr2Current = endIndex + 1;
       int[] ans = new int[arr.length];
       int ansIndx = 0;
       while (subarr1Current <= endIndex && subarr2Current < arr.length) {
           if(arr[subarr1Current] < arr[subarr2Current]) {
               ans[ansIndx++] = arr[subarr1Current++];
           } else {
               ans[ansIndx++] = arr[subarr2Current++];
           }
       }
       while (subarr1Current <= endIndex) {
           ans[ansIndx++] = arr[subarr1Current++];
       }
       while (subarr2Current < arr.length) {
           ans[ansIndx++] = arr[subarr2Current++];
       }
       for (int i = 0; i < arr.length; i++) {
           arr[i] = ans[i];
       }
   }
}