Program to merge two sorted arrays

Overview

Two arrays are given. Both are sorted

• First array is of length m+n

• Second array is of n

The objective is to merge these sorted arrays. The first array contains enough length so the first array should be modified only

Input1: [2,3,4,0,0]
Input2: [1,5]
Output: [1, 2, 3, 4, 5]

Input1: [4,5,0,0,0,0]
Input2: [1, 2, 3, 7]
Output: [1, 2, 3, 4, 5, 7]

Here is the approach we can take

• Move all elements in the first array to the end in sorted order. The first array will become

[0,0,2,3,4]

• Now start from mth index element in the first array and 0th index in the second array.

• Compare the two and place the smaller at 0th index in the first array. The first array will become

[1, 0, 2, 3, 4]

• Repeat this process. The values at the end of the first array will be placed at the front before getting overridden as we have sufficient space

Program

Here is the program for the same.

package main

import "fmt"

func merge(nums1 []int, m int, nums2 []int, n int) []int {

	if m == 0 {
		for k := 0; k < n; k++ {
			nums1[k] = nums2[k]
		}
		return nums1
	}
	nums1 = moveToEnd(nums1, m)
	i := n
	j := 0
	for k := 0; k < m+n; k++ {
		if i < m+n && j < n {
			if nums1[i] < nums2[j] {
				nums1[k] = nums1[i]
				i++
			} else {
				nums1[k] = nums2[j]
				j++
			}
		} else if j < n {
			nums1[k] = nums2[j]
			j++
		}

	}

	return nums1

}

func moveToEnd(nums []int, m int) []int {
	lenNums := len(nums)

	k := lenNums

	for i := m - 1; i >= 0; i-- {
		nums[k-1] = nums[i]
		k--
	}

	return nums
}

func main() {
	output := merge([]int{2, 3, 4, 0, 0}, 3, []int{1, 5}, 2)
	fmt.Println(output)

	output = merge([]int{4, 5, 0, 0, 0, 0}, 2, []int{1, 2, 3, 7}, 4)
	fmt.Println(output)
}

Output

[1 2 3 4 5]
[1 2 3 4 5 7]