合并排序实施检查

Question

我特别怀疑我对两种情况的合并排序的实现:

1.如果列表的大小是2,那么我已经交换了值,如果它们不是升序,否则我已经返回它们.

2.在合并函数中,当列表试图检查其中元素的数量时,我已经分配了最大的数字(9999),因此在与它进行比较的情况下总是假的.
谁能告诉我合并排序的实现是否正确？在排序完成时,但是由于案例的原因,是合并排序的实现还是错误的？

这是我的代码:
#unsorted LIST u_list = [3,6,8,1,4,7,2,12,45];

#Size of the unsorted list
global_size=len(u_list)

def foo(temp_list):
    size_of_list =len(temp_list)
#If the size of the list is 1
    if size_of_list == 1:
            return temp_list

#If the size of the list is 2
    if size_of_list == 2:
            if temp_list[0] > temp_list[1]:
                    temp_list[0],temp_list[1] = temp_list[1],temp_list[0]
                    return temp_list
            else: 
                    return temp_list


#If the size of the list is greater than 2                

    if size_of_list > 2:
            count = 1
            i = 0
            if size_of_list % 2 == 0:
                    mid1 = size_of_list/2

            else:
                    mid1 = (size_of_list/2) + 1
                    mid2 = size_of_list - mid1

            newlist1 = list()
            newlist2 = list()

            for e in temp_list:

                    if count >= mid1 + 1:
                            newlist2.append(e)
                    else:
                            newlist1.append(e)
                    if count == size_of_list:
                            break
                    count = count + 1
            sorted_list = list()
            return merge (foo(newlist1),foo(newlist2))

#Merging all the sorted components

def merge(list1,list2):

    i = 0
    j = 0
    k = 0
    size_of_list = len(list1) + len(list2)
    sorted_list = list()
    while k <= size_of_list - 1 :

            if i == len(list1):
                    list1.append(9999)
            if j == len(list2):
                    list2.append(9999)

            if list1[i] < list2[j]:
                    sorted_list.append(list1[i])
                    i = i + 1
            elif list2[j] < list1[i]:
                    sorted_list.append(list2[j])
                    j = j + 1
            k = k + 1
    return sorted_list

print foo(u_list)

Answer 1

说实话,如果我看到这样的代码,我会感到非常不安;).这可能是正确的,但我的胆量感觉不是(如果有数字> 9999怎么办？).它比必要的更复杂.语法是Python,但您没有使用Python的强大功能.

以下是我在Python中实现合并排序的方法:

def merge_sort(sequence):
    if len(sequence) < 2: 
        return sequence

    mid = int(len(sequence) / 2)
    left_sequence = merge_sort(sequence[:mid])
    right_sequence = merge_sort(sequence[mid:])
    return merge(left_sequence, right_sequence)

def merge(left, right):
    result = []
    i = j = 0
    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