Sortowanie przez scalanie

Powtórzenie: sortowania i metoda dziel i zwyciężaj - Informatyka - liceum klasa 4, zakres rozszerzony (Python)

Przypomnienie: sortowanie przez scalanie dzieli listę na połowy, sortuje je rekurencyjnie i **scala** dwie posortowane listy, biorąc zawsze mniejszy z pierwszych elementów. Działa w czasie rzędu `n log n`.

def merge(a, b):
    i = j = 0
    out = []
    while i < len(a) and j < len(b):
        if a[i] <= b[j]:
            out.append(a[i])
            i += 1
        else:
            out.append(b[j])
            j += 1
    return out + a[i:] + b[j:]

def merge_sort(a):
    if len(a) <= 1:
        return a
    middle = len(a) // 2
    return merge(merge_sort(a[:middle]), merge_sort(a[middle:]))

print(merge_sort([38, 27, 43, 3, 9, 82, 10]))

Ładowanie interaktywnego edytora... Jeśli się nie pojawi, włącz JavaScript.

Wszystkie lekcje kursu Informatyka - liceum klasa 4, zakres rozszerzony·Zaloguj się, aby zapisać postęp na koncie.