Не могу понять сортировку слиянием с python - PullRequest
Новая
       3

Не могу понять сортировку слиянием с python

0 голосов
/ 17 января 2020

Я изучаю алгоритмы, сейчас я застрял в коде сортировки слиянием. Как я понимаю, функция mergeSort () берет список и делит его на подсписок, пока его длина не станет меньше двух, что составляет всего один элемент и присваивается левой и правой переменным. После этого он передаст эти переменные в функцию merge (), которая отсортирует их влево и вправо, поместит в новый список и вернет этот список. Например, если ввод [4,3,2,1], то left = 4 right = 3, слияние (left, right, сравнить) вернет [3,4], и я застрял после этого. Пожалуйста, помогите мне понять этот пример. Спасибо. 

import operator

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

def mergeSort(L, compare = operator.lt):
    if len(L) < 2:
        return L[:]
    else:
        middle = len(L)//2
        left = mergeSort(L[:middle], compare)
        right = mergeSort(L[middle:], compare)
        return merge(left, right, compare)
...