# 486. Merge K Sorted Arrays

{% embed url="<https://www.lintcode.com/problem/merge-k-sorted-arrays/description>" %}

`Divide and conquer` 分治，两两merge，直到成为一个。

跟 Q88 的关系就像Q21 -> Q23.

{% content-ref url="88.-merge-sorted-array" %}
[88.-merge-sorted-array](https://xuqiangwen1994.gitbook.io/practice/88.-merge-sorted-array)
{% endcontent-ref %}

{% content-ref url="21.-merge-two-sorted-lists" %}
[21.-merge-two-sorted-lists](https://xuqiangwen1994.gitbook.io/practice/21.-merge-two-sorted-lists)
{% endcontent-ref %}

{% content-ref url="23.-merge-k-sorted-lists" %}
[23.-merge-k-sorted-lists](https://xuqiangwen1994.gitbook.io/practice/23.-merge-k-sorted-lists)
{% endcontent-ref %}

```python
class Solution:
    """
    @param arrays: k sorted integer arrays
    @return: a sorted array
    """
    def mergekSortedArrays(self, arrays):
        # write your code here
        def mergeTwoSortedArrays(a, b):
            res = []
            m, n = len(a), len(b)
            i, j = 0, 0
            while i < m or j < n:
                if i == m: 
                    res.append(b[j])
                    j += 1 
                elif j == n:
                    res.append(a[i])
                    i += 1 
                elif a[i] >= b[j]:
                    res.append(b[j])
                    j += 1 
                else:
                    res.append(a[i])
                    i += 1 
            return res
        
        n, skip = len(arrays), 1 
        while skip < n:
            for a in range(0, n-skip, skip*2):
                arrays[a] = mergeTwoSortedArrays(arrays[a], arrays[a+skip])
            skip *= 2 
        return arrays[0]
```
