Merge Sorted Array

Data Structures and Algorithms

Statement

Given two sorted integer arrays, nums1 and nums2, and the number of values of each array, m and n, merge the second array into the first one. Assume nums1 has length m + n. Modify nums1 in place.

Constraints

• nums1.length() = m + n
• nums2.length() = n
• 0 ≤ m, n ≤ 200
• 1 ≤ m + n ≤ 200
• -10³ ≤ nums1[i], nums2[j] ≤ 10³

Solution

"""
production algorithm
"""


class Solution:
    def merge_sorted(self, nums1, m, nums2, n):
        """
        time complexity O(n)
        space complexity O(1)
        """
        i, j, k = m - 1, n - 1, m + n - 1

        # reverse iteration of both arrays
        while 0 <= i and 0 <= j:
            if nums2[j] < nums1[i]:
                nums1[k], i, k = nums1[i], i - 1, k - 1
            else:
                nums1[k], j, k = nums2[j], j - 1, k - 1

        # reverse iteration remainder of first array
        while 0 <= i:
            nums1[k], i, k = nums1[i], i - 1, k - 1

        # reverse iteration remainder of second array
        while 0 <= j:
            nums1[k], j, k = nums2[j], j - 1, k - 1

        return nums1

"""
unit tests
"""

from unittest import TestCase
from algorithms.k_way_merge.merge_sorted_array.solution import Solution


class SolutionTestCase(TestCase):
    def test_first_array_greater_length(self):
        # Given
        nums1 = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 0, 0, 0, 0, 0]
        nums2 = [2, 4, 6, 8, 10]
        m, n = 10, 5
        solution = Solution()

        # When
        actual = solution.merge_sorted(nums1, m, nums2, n)

        # Then
        expected = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19]
        self.assertEqual(actual, expected)

    def test_second_array_greater_length(self):
        # Given
        nums1 = [1, 3, 5, 7, 9, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
        nums2 = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]
        m, n = 5, 10
        solution = Solution()

        # When
        actual = solution.merge_sorted(nums1, m, nums2, n)

        # Then
        expected = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 14, 16, 18, 20]
        self.assertEqual(actual, expected)

Strategy

K-way Merge.

Explanation

Both input arrays are sorted, so they can be iterated in reverse to find the next greatest value to insert at the end of the first array. After completion of iteration of one of the arrays, then complete iteration of the other array. After both iterations, the two arrays will be merged.

Time Complexity

The values of both arrays are iterated. The number of values of the first array is m, and the number of values of the second array is n. Therefore the time complexity of the algorithm is O(m + n).

Space Complexity

The auxiliary space complexity of the algorithm is O(1).

Links

data_structures_algorithms/algorithms/k_way_merge/merge_sorted_array at main ·…