Merge Sorted Array

Introduction

Merging two sorted arrays is a common problem in computer science. In this problem, we are given two sorted arrays and we need to merge them into a single sorted array. However, the twist is that we are not allowed to use any extra space to store the merged array.

Problem Statement

Given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively. Merge nums1 and nums2 into a single array sorted in non-decreasing order. The final sorted array should be stored inside the array nums1.

Algorithmic Approach

To solve this problem, we can start by comparing the last elements of both arrays and merging them into the last position of the nums1 array. We will repeat this process until all elements of the two arrays have been merged. Finally, we will have a single sorted array nums1.

Implementation

 void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i = m-1, j = n-1, k = m+n-1;
        while (i >= 0 && j >= 0) {
            if (nums1[i] > nums2[j]) {
                nums1[k--] = nums1[i--];
            } else {
                nums1[k--] = nums2[j--];
            }
        }
        while (j >= 0) {
            nums1[k--] = nums2[j--];
        }
    }

Time Complexity

The time complexity of the algorithm is O(m+n), where m is the number of elements in nums1 and n is the number of elements in nums2. This is because the algorithm needs to iterate over both arrays to merge them, and the amount of work done in each iteration depends on the length of the arrays. Specifically, the algorithm uses a two-pointer approach to compare the values in the two arrays and place them in the correct order in nums1.

Space Complexity

The space complexity of the algorithm is O(1), because it does not use any extra memory proportional to the size of the input. Instead, it uses the space in nums1 that is already allocated, so the space used by the algorithm is constant with respect to the input size.

Conclusion

In this blog, we have discussed the problem of merging two sorted arrays in place. We have also presented an algorithmic approach to solve this problem and analyzed its time and space complexity.