Merge Sort

Merge sort is based on the operation of an efficient merge sort algorithm, which is a very typical application of divide and conquer (Divide and Conquer) adoption. The merger has been ordered sequences, fully ordered sequence; which is to make each child an orderly sequence, and then make inter-segment orderly sequence. If two ordered tables are combined into a sorted list, called Road merge.

Merging process: Compare a [i] and a [j] size, if a [i] ≤a [j], then the first element of an ordered list a [i] is copied to r [k] in and so i and k, respectively, plus 1; otherwise, the second ordered list of elements a [j] is copied to r [k] in, and let j and k, respectively, plus 1, so the cycle continues, until one of them ordered to take complete copy a table and then another table ordered the remaining elements to r from subscript subscript t k to the unit. Merge sort we usually use recursive algorithm, the first to be sorted interval [s, t] to the midpoint of two points, then the left subinterval sort, then sort the right side of the sub-interval, the last section of the left and right interval with a merge operation combined into ordered interval [s, t].

def merge(left, right):
i, j = 0, 0
result = []
while i < len(left) and j < len(right):
    if left[i] <= right[j]:
        result.append(left[i])
        i += 1
    else:
        result.append(right[j])
        j += 1
result += left[i:]
result += right[j:]
return result

def merge_sort(lists):
    # 归并排序
    if len(lists) <= 1:
        return lists
    num = len(lists) / 2
    left = merge_sort(lists[:num])
    right = merge_sort(lists[num:])
    return merge(left, right)