Merging Sorted Containers¶
Before considering K-way merge, let us first look at the simpler version of the problem.
The 2-Way merge problem.¶
Merging two sorted arrays¶
Given 2 integer arrays, sorted in non decreasing order, merge them into a single sorted array.
Code
from typing import List
def merge_two(arr1 : List[int], arr2 : List[int]) -> List[int] :
"""
Given two arrays sorted in non decreasing order, return a merged array
"""
m, n = len(arr1) , len(arr2)
res = [0]*(m+n)
p1,p2,p3 = 0,0,0
while p1 < m and p2 < n :
if arr1[p1] < arr2[p2] :
res[p3] = arr1[p1]
p3+=1
p1+=1
else :
res[p3] = arr2[p2]
p3+=1
p2+=1
while p1 < m :
res[p3] = arr1[p1]
p1+=1
p3+=1
while p2 < n :
res[p3] = arr2[p2]
p2+=1
p3+=1
return res
if __name__ == "__main__" :
print(merge_two([4,5,7] , [3,6,7,8]))
print(merge_two([4,5,7] , [3,6]))
print(merge_two([] , [1,2,3]))
print( merge_two( [1, 2, 2, 5] , [2, 3, 4, 4] ) ) # [1, 2, 2, 2, 3, 4, 4, 5]
print( merge_two( [1, 3, 5, 7] , [2, 4, 6, 8] ) ) # [1, 2, 3, 4, 5, 6, 7, 8]
"""
Unit Tests for Two way merge.
# Aside : See these for an introduction to pytest : https://realpython.com/pytest-python-testing/
https://gist.github.com/kwmiebach/3fd49612ef7a52b5ce3a
"""
import pytest
from two_way_merge import merge_two
# --- Test Cases ---
def test_merge_basic():
"""Tests merging two non-empty lists."""
arr1 = [1, 3, 5, 7]
arr2 = [2, 4, 6, 8]
expected = [1, 2, 3, 4, 5, 6, 7, 8]
# Note: The original buggy code might return [1, 2, 3, 4, 5, 6, 7, 9]
assert merge_two(arr1, arr2) == expected
def test_merge_empty_first():
"""Tests merging when the first list is empty."""
arr1 = []
arr2 = [2, 4, 6]
expected = [2, 4, 6]
assert merge_two(arr1, arr2) == expected
# Test swap logic too
assert merge_two(arr2, arr1) == expected
def test_merge_empty_second():
"""Tests merging when the second list is empty."""
arr1 = [1, 3, 5]
arr2 = []
expected = [1, 3, 5]
assert merge_two(arr1, arr2) == expected
# Test swap logic too
assert merge_two(arr2, arr1) == expected
def test_merge_both_empty():
"""Tests merging when both lists are empty."""
arr1 = []
arr2 = []
expected = []
assert merge_two(arr1, arr2) == expected
def test_merge_duplicates():
"""Tests merging lists with duplicate numbers."""
arr1 = [1, 2, 2, 5]
arr2 = [2, 3, 4, 4]
expected = [1, 2, 2, 2, 3, 4, 4, 5]
# Note: Original buggy code might return [1, 2, 2, 2, 3, 4, 4, 9]
assert merge_two(arr1, arr2) == expected
def test_merge_duplicates_across_lists():
"""Tests merging lists where duplicates exist between lists."""
arr1 = [1, 3, 5]
arr2 = [1, 3, 5]
expected = [1, 1, 3, 3, 5, 5]
# Note: Original buggy code might return [1, 1, 3, 3, 5, 9]
assert merge_two(arr1, arr2) == expected
def test_merge_interleaved():
"""Tests merging lists with highly interleaved numbers."""
arr1 = [1, 4, 5, 8]
arr2 = [2, 3, 6, 7]
expected = [1, 2, 3, 4, 5, 6, 7, 8]
# Note: Original buggy code might return [1, 2, 3, 4, 5, 6, 7, 9]
assert merge_two(arr1, arr2) == expected
def test_merge_one_list_much_shorter():
"""Tests merging when one list is significantly shorter."""
arr1 = [1, 2, 10, 11, 12]
arr2 = [3, 4]
expected = [1, 2, 3, 4, 10, 11, 12]
# Note: Original buggy code might return [1, 2, 3, 4, 10, 11, 9]
assert merge_two(arr1, arr2) == expected
# Test swap logic too
assert merge_two(arr2, arr1) == expected # Should give same result
def test_merge_all_elements_smaller():
"""Tests merging when all elements of one list are smaller than the other."""
arr1 = [1, 2, 3]
arr2 = [4, 5, 6]
expected = [1, 2, 3, 4, 5, 6]
# Note: Original buggy code might return [1, 2, 3, 4, 5, 9]
assert merge_two(arr1, arr2) == expected
# Test swap logic too
assert merge_two(arr2, arr1) == expected # Should give same result
def test_merge_negative_numbers():
"""Tests merging lists with negative numbers."""
arr1 = [-5, -1, 0, 10]
arr2 = [-3, -2, 8, 12]
expected = [-5, -3, -2, -1, 0, 8, 10, 12]
# Note: Original buggy code might return [-5, -3, -2, -1, 0, 8, 10, 9]
assert merge_two(arr1, arr2) == expected
def test_merge_single_element_lists():
"""Tests merging lists with single elements."""
arr1 = [5]
arr2 = [2]
expected = [2, 5]
# Note: Original buggy code might return [2, 9] due to off-by-one loop
assert merge_two(arr1, arr2) == expected
assert merge_two(arr2, arr1) == expected
Merging two sorted lists¶
The same thing for a linked list :
Code
"""
Solution for https://leetcode.com/problems/merge-two-sorted-lists/description/
"""
from typing import Optional
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
p1, p2 = list1,list2
dummy = ListNode(0)
p3 = dummy
while p1 and p2 :
if p1.val < p2.val:
p3.next = p1
p1 = p1.next
else:
p3.next = p2
p2 = p2.next
p3 = p3.next
if p1 :
p3.next = p1
else :
p3.next = p2
return dummy.next
So, how are we solving the problem of two way merging?
We have a write pointer p3 and we have two read pointers, p1 and p2. In each iteration of the while loop, we pick the smaller read pointer to write to the write location and move both pointers (write pointer and one of the read pointers) ahead.
If either p1 or p2 have still not reached the end of their read containers, we just write the rest of that read container at the write pointer.
Practice¶
Merge sorted arrays backwards
"""
Solution for https://leetcode.com/problems/merge-sorted-array/
A slightly different variation of the two-way merge problem.
The challenge here is to merge one array into another array
backwards into extra space allocated at the end of one of the arrays.
To accomplish this at each step we pick the greatest among the the two choices and put it at the end of the target array.
p3 -> write pointer
p1, p2 -> read pointers
nums1 -> target array
p3 will never overwrite p1 because :
Initially p3 - p1 = n,
If p2 is decremented, the gap p3 - p1 reduces by 1, because p3 is incremented and p1 remains the same.
If p1 is decremented, the gap p3 - p1 remains the same
0<= p3-p1 <= n # The gap can at most become zero.
When,
p3 -p1 = 0 <-> p2 = -1
Which means all of nums2 has been written into nums1, the while loop will not execute.
Therefore p3 will never overwrite p1.
Dry Run these to see how it works out :
nums1 :[2,3,0]
nums2 :[4]
nums1 :[2,3,0]
nums2 : [-1]
"""
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
p1,p2,p3 = m-1, n-1, len(nums1) -1
while p2 >= 0 :
if p1 >=0 and nums1[p1] > nums2[p2] :
nums1[p3] = nums1[p1]
p1-=1
p3-=1
else :
nums1[p3] = nums2[p2]
p2-=1
p3-=1
return nums1
Merge Strings Alternately
"""
A simpler version of the two way merge problem.
All you have to do is pick the next element alternately among the two choices.
The EFFECT can be achieved by simply picking a letter from each array one after the other.
Wrap this up in s while loop runs until either one of the arrays have not finished being read.
"""
class Solution:
def mergeAlternately(self, word1: str, word2: str) -> str:
res = []
p1,p2 =0,0
while p1 < len(word1) or p2 < len(word2) :
if p1 < len(word1) :
res.append(word1[p1])
p1+=1
if p2 < len(word2) :
res.append(word2[p2])
p2+=1
return "".join(res)