Merge Two Sorted Array in Place

# 問題

共に昇順に整列された配列aと配列bが与えられる．aにはbの要素を全て格納するほどのバッファが存在する．このとき，追加のメモリを使用せずにaとbを昇順に整列された状態にマージせよ．

# 答え

後ろからやる．

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
a = [1, 3, 4, 8, 10, -1, -1, -1, -1]
b = [2, 7, 11, 14]

def sorted_merge(a, b, tail_a, tail_b):
    idx_a = tail_a - 1
    idx_b = tail_b - 1
    idx_merged = tail_a + tail_b - 1
    while 0 <= idx_b:
        if 0 <= idx_a and b[idx_b] < a[idx_a]:
            a[idx_merged] = a[idx_a]
            idx_a -= 1
        else:
            a[idx_merged] = b[idx_b]
            idx_b -= 1
        idx_merged -= 1

sorted_merge(a, b, 5, 4)
print(a) # => [1, 2, 3, 4, 7, 8, 10, 11, 14]