小的列表排序，归并性能一般呀。

 

# coding = utf-8


# ========归并排序========
def merge_sort(a_list):
    loop_count = 0
    print('Splitting ', a_list)

    if len(a_list) > 1:
        loop_count += 1
        mid = len(a_list) // 2
        left_half = a_list[:mid]
        right_half = a_list[mid:]

        merge_sort(left_half)
        merge_sort(right_half)

        i = 0
        j = 0
        k = 0
        while i < len(left_half) and j < len(right_half):
            loop_count += 1
            if left_half[i] < right_half[j]:
                a_list[k] = left_half[i]
                i += 1
            else:
                a_list[k] = right_half[j]
                j += 1
            k += 1
        while i < len(left_half):
            loop_count += 1
            a_list[k] = left_half[i]
            i += 1
            k += 1
        while j < len(right_half):
            loop_count += 1
            a_list[k] = right_half[j]
            j += 1
            k += 1
    print('Merging ', a_list)
    print('======== shell_sort loop_count========', loop_count)


my_list = [4, 5, 7, 2, 9, 7, 9, 54, 765, 45, 9876, 34, 12343, 36]
merge_sort(my_list)
print(my_list)

　　

D:\cheng\test\Scripts\python.exe D:/GIT/Prism4K/Prism4K/document/tests.py
Splitting  [4, 5, 7, 2, 9, 7, 9, 54, 765, 45, 9876, 34, 12343, 36]
Splitting  [4, 5, 7, 2, 9, 7, 9]
Splitting  [4, 5, 7]
Splitting  [4]
Merging  [4]
======== shell_sort loop_count======== 0
Splitting  [5, 7]
Splitting  [5]
Merging  [5]
======== shell_sort loop_count======== 0
Splitting  [7]
Merging  [7]
======== shell_sort loop_count======== 0
Merging  [5, 7]
======== shell_sort loop_count======== 3
Merging  [4, 5, 7]
======== shell_sort loop_count======== 4
Splitting  [2, 9, 7, 9]
Splitting  [2, 9]
Splitting  [2]
Merging  [2]
======== shell_sort loop_count======== 0
Splitting  [9]
Merging  [9]
======== shell_sort loop_count======== 0
Merging  [2, 9]
======== shell_sort loop_count======== 3
Splitting  [7, 9]
Splitting  [7]
Merging  [7]
======== shell_sort loop_count======== 0
Splitting  [9]
Merging  [9]
======== shell_sort loop_count======== 0
Merging  [7, 9]
======== shell_sort loop_count======== 3
Merging  [2, 7, 9, 9]
======== shell_sort loop_count======== 5
Merging  [2, 4, 5, 7, 7, 9, 9]
======== shell_sort loop_count======== 8
Splitting  [54, 765, 45, 9876, 34, 12343, 36]
Splitting  [54, 765, 45]
Splitting  [54]
Merging  [54]
======== shell_sort loop_count======== 0
Splitting  [765, 45]
Splitting  [765]
Merging  [765]
======== shell_sort loop_count======== 0
Splitting  [45]
Merging  [45]
======== shell_sort loop_count======== 0
Merging  [45, 765]
======== shell_sort loop_count======== 3
Merging  [45, 54, 765]
======== shell_sort loop_count======== 4
Splitting  [9876, 34, 12343, 36]
Splitting  [9876, 34]
Splitting  [9876]
Merging  [9876]
======== shell_sort loop_count======== 0
Splitting  [34]
Merging  [34]
======== shell_sort loop_count======== 0
Merging  [34, 9876]
======== shell_sort loop_count======== 3
Splitting  [12343, 36]
Splitting  [12343]
Merging  [12343]
======== shell_sort loop_count======== 0
Splitting  [36]
Merging  [36]
======== shell_sort loop_count======== 0
Merging  [36, 12343]
======== shell_sort loop_count======== 3
Merging  [34, 36, 9876, 12343]
======== shell_sort loop_count======== 5
Merging  [34, 36, 45, 54, 765, 9876, 12343]
======== shell_sort loop_count======== 8
Merging  [2, 4, 5, 7, 7, 9, 9, 34, 36, 45, 54, 765, 9876, 12343]
======== shell_sort loop_count======== 15
[2, 4, 5, 7, 7, 9, 9, 34, 36, 45, 54, 765, 9876, 12343]

Process finished with exit code 0