package main

import "fmt"

func Merge(a []int, b []int, m, n int) error {
    if len(a) != m+n {
        return fmt.Errorf("bad req")
    }
    if len(b) != n {
        return fmt.Errorf("bad req")
    }
    if m+n == 0 {
        return nil
    }
    curResPos := 0
    curAPos := 0
    curBPos := 0
    for {
        if curBPos == n { // B 消耗完了
            for curAPos != curBPos {
                a[curResPos] = b[curAPos]
                curResPos++
                curAPos++
            }
        }
        if curResPos == m+curBPos { // A 消耗完了
            for curBPos != n {
                a[curResPos] = b[curBPos]
                curResPos++
                curBPos++
            }
        }
        if curResPos == m+n{
            break
        }
        aVal := a[curResPos+1]
        if curAPos != curBPos {
            aVal = b[curAPos]
        }
        bVal := b[curBPos]
        if aVal < bVal { // A 小
            valToMove := a[curResPos+1]
            if curAPos != curBPos { // A 的头在 B 暂存
                nextVal := b[curAPos]
                b[curAPos] = valToMove // 把将要被覆盖的值和 A 的头交换
                a[curResPos+1] = nextVal
                curResPos++
            } else { // A 的头就在 A
                curResPos++ // 直接向前
            }
        } else { // B 大交换一下
            valToMove := a[curResPos+1]
            nextVal := b[curBPos]
            a[curResPos+1] = nextVal
            b[curBPos] = valToMove
            curResPos++
            curBPos++
        }
    }
    return nil
}

func main() {
    num1 := []int{1, 2, 3, 0, 0, 0}
    num2 := []int{2, 5, 6}
    Merge(num1,num2,3,3)
    fmt.Printf("%v",num1)
}