Merge Sorted Array

Problem Statement

deeksha sharma
Algorithm Problems
2 min readNov 30, 2015

--

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1and nums2 are m and n respectively.

Approach

  • If nums1 and nums2 are empty then return. Nothing cane be merged.
  • Copy m elements from nums1 into a new array say nums1Replica.
  • Initialize the indexes of all 3 arrays to 0:
  • Index of nums1Replica is i
  • Index of nums2 is j
  • Index of nums1 is k
  • Start to compare each element in nums1Replica and nums2 until i and j are less than m and n respectively.
  • If nums1Replica[i] <= nums2[j], copy nums1Replica[i] into nums1[k] & increment i, k
  • If nums1Replica[i] > nums2[j], copy nums2[j] into nums1[k] & increment j, k
  • When either i >= m OR j >= n, copy the remaining array into nums1 (sorted array).

Run Time Complexity

Worst case run time complexity is O(n) which includes:

Copying m elements into a new array = O(n)

Traversing through nums1Replica and nums2 = O(n)

Copying the remaining elements into the sorted array = O(n)

Code

--

--

deeksha sharma
Algorithm Problems

Work for https://bonsaiilabs.com/ life long learner ,investing time heavily in personal finance, education, tech and design skills. Twitter: @deekshasharma25