我是否创建了合并排序算法

Question

我刚刚尝试制作归并排序算法。我将它与我在 Geeks for Geeks 上找到的一个进行了比较，它们看起来不太相似。我想知道我是否使合并排序算法正确，或者我是否创建了不同的算法？这两个算法的效率是一样的，所以我猜算法的一部分是正确的？

import random
import copy
import time

data_size = 10000
unsorted_array = random.sample(range(0, data_size), data_size)

# My version
def mergeSort(arr):
    split = []
    # Takes two and two elements from the array
    # It then puts the smallest item first in the new 
    # Returns an array consisting of smaller subarrays with two items each
    for i in range(len(arr) // 2):
        if arr[2*i] > arr[2*i+1]:
            arr[2*i], arr[2*i+1] = arr[2*i+1], arr[2*i]
        split.append([arr[2*i], arr[2*i+1]])

    # If the number of items are odd
    if len(split) != len(arr) / 2:
        split.append([arr[-1]])

    result = divide(split)
    print(result)

def divide(arr):
    i = 0
    new_arr = []
    # Merges two and two parts of the array
    while i < len(arr) // 2:
        new_arr.append(merge(arr[2*i], arr[2*i+1]))
        i += 1
    # The original array had an odd
    # number of element
    if len(new_arr) != len(arr) / 2:
        new_arr.append(arr[-1])

    # The array is not fully merged
    # The process must be repetead
    if len(new_arr) != 1:
        new_arr = divide(new_arr)

    #Return the final array
    return new_arr

def merge(left, right):
    merged = []
    total_len = len(left) + len(right)
    left_i = 0
    right_i = 0
    while len(merged) != total_len:  # Repeat until all elements of org. is merged
        if left_i < len(left):  # Check if all elements of left array has been added
            if right_i < len(right):  # Check if all elements of right array has been added
                # Add the smallest element to the merged list
                if right[right_i] > left[left_i]:
                    merged.append(left[left_i])
                    left_i += 1
                else:
                    merged.append(right[right_i])
                    right_i += 1
            else:  # Add left element, all right elements have been added
                merged.append(left[left_i])
                left_i += 1
        else:  # Add right array element, all left elements have been added
            merged.append(right[right_i])
            right_i += 1

    return merged

# From GeeksForGeeks
def mergeSort_web(arr): 
    if len(arr) > 1: 
        mid = len(arr) // 2 #Finding the mid of the array 
        L = arr[:mid] # Dividing the array elements  
        R = arr[mid:] # into 2 halves 

        mergeSort_web(L) # Sorting the first half 
        mergeSort_web(R) # Sorting the second half 

        i = j = k = 0

        # Copy data to temp arrays L[] and R[] 
        while i < len(L) and j < len(R): 
            if L[i] < R[j]: 
                arr[k] = L[i] 
                i += 1
            else: 
                arr[k] = R[j] 
                j += 1
            k += 1

        # Checking if any element was left 
        while i < len(L): 
            arr[k] = L[i] 
            i += 1
            k += 1

        while j < len(R): 
            arr[k] = R[j] 
            j += 1
            k += 1

start_time = time.time()
#mergeSort(unsorted_array)
mergeSort_web(unsorted_array)
# print(unsorted_array) # Only enable for the web version 
print("--- %s seconds ---" % (time.time() - start_time))

Answer 1

您编写的代码确实可以用作归并排序。但是，它与您发布的网络版本有一些差异。 GeeksforGeeks 版本以递归方式工作，因此您将首先对左半部分进行排序，然后对右半部分进行排序。而您的代码是自下而上工作的，一次将相同大小的列表放在一起。两者时间复杂度相等，主要原理相同

我是否创建了合并排序算法

Have I created the mergesort algorithm

python

sorting

algorithm

mergesort