k-way与分而治之合并？

Question

这个想法是将第一个k/2列表和第二个k/2列表进行递归合并，然后将两个合并列表合并到一个列表中并返回。

我对第一个k/2与第二个k/2列表递归合并意味着什么感到困惑。 任何人都可以澄清这一点，或者可以去解释这个递归的一些伪代码？

Answer 1

List recursiveMerge(List[] lists) 
{ 
    // Easy to solve problem for up to length 2 
    if (lists.length < 1) 
    { 
    return new List(); 
    } 
    if (lists.length == 1) 
    { 
    return lists[0]; 
    } 
    if (lists.length == 2) 
    { 
    return baseMerge(lists[0], lists[1]); 
    } 
    // For longer lengths split the array into two 
    int half = lists.length/2; 
    List[] firstHalf = new List[half]; 
    List[] secondHalf = new List[lists.length - half]; 
    System.arraycopy(lists, 0, firstHalf, 0, firstHalf.length); 
    System.arraycopy(lists, firstHalf.length, secondHalf, 
    0, secondHalf.length); 
    // Solve the problem separately in each sub-array 
    List a = recursiveMerge(firstHalf); 
    List b = recursiveMerge(secondHalf); 
    // and produce a combined solution 
    return baseMerge(a, b); 
}