Merge Sort#

Merge Sort的Python实现

 1def merge(l1, l2):
 2    result = []
 3
 4    i = j = 0
 5
 6    while i < len(l1) and j < len(l2):
 7
 8        if l1[i] > l2[j]:
 9            result.append(l2[j])
10            j += 1
11
12        elif l1[i] < l2[j]:
13            result.append(l1[i])
14            i += 1
15        else:
16            result.append(l1[i])
17            result.append(l2[j])
18            i += 1
19            j += 1
20
21    while i < len(l1):
22        result.append(l1[i])
23        i += 1
24
25    while j < len(l2):
26        result.append(l2[j])
27        j += 1
28
29    return result
30
31
32def merge_sort(my_list):
33
34    if len(my_list) == 1:
35        return my_list
36
37    mid_index = int(len(my_list) / 2)
38
39    left = merge_sort(my_list[:mid_index])
40    right = merge_sort(my_list[mid_index:])
41
42    return merge(left, right)
43
44
45result = merge_sort([6, 6, 3, 1, 8, 7, 2, 6])
46print(result)