Merge Sorted Array
Explore the process of merging two sorted arrays into a single sorted array using efficient in-place methods. This lesson helps you understand how to handle arrays of different sizes and combine them while maintaining order, preparing you for coding interview problems involving sorting and merging. Gain practical experience by implementing and testing this pattern to enhance your algorithm skills.
We'll cover the following...
Statement
You are given two integer arrays, nums1 and nums2, both sorted in non-decreasing order. You are also given two integers, m and n, representing the number of elements in nums1 and nums2, respectively.
Your task is to merge the elements of nums2 into nums1 so that nums1 becomes a single array sorted in non-decreasing order.
The merged result is stored in nums1, which has a total length of m + n. The first m positions contain the initial elements, the last n positions are placeholders (initialized to 0), and nums2 contains the n elements to merge.
Constraints:
nums1.lengthnums2.length-
nums1[i],nums2[j]
Examples
Understand the problem
Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:
Merge Sorted Array
What is the output if the following arrays and values of and are given as input?
nums1 = [1, 2, 7, 92, 0, 0, 0], m = 4
nums2 = [3, 4, 5], n = 3
[1, 2, 3, 4, 5, 7, 92]
[1, 2, 7, 92, 3, 4, 5]
[3, 4, 5, 1, 2, 7, 92]
Figure it out!
We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.
Try it yourself
Implement your solution in the following coding playground.
public class MergeSorted{public static int[] mergeSorted(int[] nums1, int m, int[] nums2, int n) {// Replace this placeholder return statement with your codeint[] list = new int[]{};return list;}}