Sortowanie przez scalanie: podziel, posortuj, scal
Zaimplementują Państwo rekurencyjne sortowanie przez scalanie, prześledzą drzewo algorytmu dziel i zwyciężaj oraz wyjaśnią, dlaczego we wszystkich przypadkach gwarantuje ono O(n log n).
Sortowanie przez scalanie: podziel, posortuj, scal to bezpłatna lekcja Coding Interview Prep na CoddyKit. To lekcja 2 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Intuicja stojąca za metodą dziel i zwyciężaj
Sortowanie przez scalanie to klasyczny algorytm dziel i zwyciężaj: podziel tablicę na połowy, rekurencyjnie posortuj każdą z nich, a następnie scal obie posortowane połowy w jeden posortowany wynik. Kluczowa obserwacja jest taka, że scalanie dwóch posortowanych tablic ma złożoność O(n) — jest znacznie tańsze niż sortowanie od początku. Taki podział tworzy drzewo rekurencji o log n poziomach, z których każdy wymaga O(n) pracy związanej ze scalaniem, co daje optymalną dla sortowania przez porównania granicę O(n log n).
# High-level merge sort structure
def merge_sort(arr):
# Base case: 0 or 1 element already sorted
if len(arr) <= 1:
return arr
# Divide
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # sort left half
right = merge_sort(arr[mid:]) # sort right half
# Conquer (merge)
return merge(left, right)
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
# [3, 9, 10, 27, 38, 43, 82]Wyjaśnienie etapu scalania
Podczas scalania dwóch posortowanych tablic należy utrzymywać dwa wskaźniki — po jednym dla każdej połowy. Porównuj pierwsze elementy; kopiuj mniejszy z nich do wyniku i przesuwaj odpowiadający mu wskaźnik. Gdy jedna połowa zostanie wyczerpana, bezpośrednio skopiuj pozostałą część drugiej. Operacja ta działa w czasie O(n) i wymaga O(n) pamięci na tablicę wynikową. Etap scalania jest algorytmicznym sercem sortowania przez scalanie — należy go dobrze zrozumieć.
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # <= preserves stability
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
# Append remaining elements
result.extend(left[i:])
result.extend(right[j:])
return result
print(merge([1,3,5,7], [2,4,6,8]))
# [1, 2, 3, 4, 5, 6, 7, 8]Pełna implementacja sortowania przez scalanie
Połączenie dzielenia i scalania: wywołania rekurencyjne dzielą problem na połowy, aż pozostaną pojedyncze elementy (trywialnie posortowane), a następnie wywołania scalania łączą je z powrotem. Na każdym poziomie drzewa rekurencji scalane jest łącznie tych samych n elementów (rozłożonych na wiele scaleń). Głębokość rekurencji wynosi log₂(n), co daje łączny czas O(n log n) oraz O(n) pomocniczej pamięci na tablice wynikowe scalania i dodatkowo O(log n) głębokości stosu wywołań.
def merge_sort_full(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort_full(arr[:mid])
right = merge_sort_full(arr[mid:])
# Merge the two sorted halves
merged = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: merged.append(left[i]); i += 1
else: merged.append(right[j]); j += 1
merged.extend(left[i:] + right[j:])
return merged
print(merge_sort_full([5,2,4,6,1,3,2,6]))
# [1, 2, 2, 3, 4, 5, 6, 6]Drzewo rekurencji sortowania przez scalanie
Wyobraźmy sobie drzewo rekurencji sortowania przez scalanie dla n=8: poziom 0 zawiera jedną tablicę z 8 elementami; poziom 1 — dwie tablice po 4 elementy; poziom 2 — cztery tablice po 2 elementy; poziom 3 — osiem pojedynczych elementów (przypadki bazowe). Podczas powrotu w górę poziom 3→2 scala łącznie 8 elementów, poziom 2→1 również 8, a poziom 1→0 także 8. Daje to 3 poziomy × 8 elementów = 24 operacje ≈ 8 × log₂(8) = 24. Potwierdza to złożoność O(n log n).
# Trace the tree depth
level_work = []
def merge_sort_traced(arr, depth=0):
if depth >= len(level_work):
level_work.append(0)
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort_traced(arr[:mid], depth+1)
right = merge_sort_traced(arr[mid:], depth+1)
level_work[depth] += len(arr) # track merge work
merged = sorted(left + right) # simplified merge
return merged
merge_sort_traced(list(range(8, 0, -1)))
for d, work in enumerate(level_work):
print(f'Level {d}: {work} elements merged')Sortowanie przez scalanie w miejscu
Standardowe rekurencyjne sortowanie przez scalanie przydziela O(n) pomocniczej pamięci na wynik scalania. Istnieje sortowanie przez scalanie w miejscu, ale jest ono złożone i ma duże stałe — rzadko pojawia się na rozmowach kwalifikacyjnych. Częste pytanie dodatkowe brzmi: „Czy można wykonać sortowanie przez scalanie przy użyciu O(1) dodatkowej pamięci?”. Prawidłowa odpowiedź: „Teoretycznie tak, ale praktyczne implementacje wymagają albo O(n) pamięci, albo zwiększają złożoność; Pythonowy Timsort używa O(n) pamięci podczas scalania”.
# Bottom-up merge sort: iterative, avoids recursion stack
def merge_sort_bottomup(arr):
n = len(arr)
width = 1
while width < n:
for i in range(0, n, 2 * width):
left = arr[i:i+width]
right = arr[i+width:i+2*width]
# Merge and put back
merged = []
a, b = 0, 0
while a < len(left) and b < len(right):
if left[a] <= right[b]: merged.append(left[a]); a+=1
else: merged.append(right[b]); b+=1
merged += left[a:] + right[b:]
arr[i:i+len(merged)] = merged
width *= 2
return arr
print(merge_sort_bottomup([5,2,4,6,1,3]))
# [1, 2, 3, 4, 5, 6]Sortowanie przez scalanie jest stabilne
Sortowanie przez scalanie jest stabilne: równe elementy z lewej połowy zawsze występują przed równymi elementami z prawej połowy w scalonym wyniku. Gwarantuje to użycie <= (a nie <) przy wyborze elementu z lewej strony. Stabilność ma znaczenie przy sortowaniu wielokryterialnym. Wbudowane funkcje Pythona sorted() i list.sort() używają algorytmu Timsort, który również jest stabilny i ma złożoność O(n log n), dlatego stanowią bezpieczny wybór w kodzie produkcyjnym.
# Demonstrating stability: sort (value, original_index) pairs
items = [(3,'A'), (1,'B'), (3,'C'), (2,'D')]
# Sort by value only
result = merge_sort_full(items) # won't work directly
# Use Python's stable sort:
result = sorted(items, key=lambda x: x[0])
print(result)
# [(1,'B'),(2,'D'),(3,'A'),(3,'C')]
# 'A' comes before 'C' for value=3 (stable order)Scalanie k posortowanych tablic
Scalenie k posortowanych tablic zawierających łącznie n elementów można wykonać, wielokrotnie scalając pary (jak w drabince turniejowej), w czasie O(n log k). Każdy poziom scalania przetwarza n elementów, a poziomów jest log k. Alternatywnie można użyć kopca minimum o rozmiarze k: umieścić w nim najmniejszy pozostały element z każdej tablicy, pobierać minimum, a następnie dodawać kolejny element z tej samej tablicy. Podejście z kopcem również ma złożoność O(n log k), ale zużywa mniej pamięci, gdy k jest bardzo duże.
import heapq
def merge_k_sorted(arrays):
result = []
heap = []
# Push first element from each array with array index
for i, arr in enumerate(arrays):
if arr:
heapq.heappush(heap, (arr[0], i, 0))
while heap:
val, arr_i, elem_i = heapq.heappop(heap)
result.append(val)
if elem_i + 1 < len(arrays[arr_i]):
next_val = arrays[arr_i][elem_i + 1]
heapq.heappush(heap, (next_val, arr_i, elem_i+1))
return result
arrs = [[1,4,7],[2,5,8],[3,6,9]]
print(merge_k_sorted(arrs)) # [1,2,3,4,5,6,7,8,9]Zliczanie inwersji za pomocą sortowania przez scalanie
Zliczanie inwersji (par, dla których a[i] > a[j] oraz i < j) w czasie O(n log n) wykorzystuje zmodyfikowane sortowanie przez scalanie. Podczas etapu scalania, gdy element z prawej podtablicy jest mniejszy od elementu z lewej podtablicy, tworzy inwersję z każdym pozostałym elementem lewej podtablicy. W tym momencie należy dodać len(left) - i do licznika.
def count_inversions(arr):
if len(arr) <= 1:
return arr, 0
mid = len(arr) // 2
left, l_inv = count_inversions(arr[:mid])
right, r_inv = count_inversions(arr[mid:])
merged = []
inversions = l_inv + r_inv
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i]); i += 1
else:
merged.append(right[j]); j += 1
inversions += len(left) - i # all remaining left elements > right[j]
merged.extend(left[i:] + right[j:])
return merged, inversions
_, inv = count_inversions([3, 1, 2])
print(inv) # 2: (3,1) and (3,2)Sortowanie przez scalanie a quicksort
Sortowanie przez scalanie gwarantuje O(n log n) w każdym przypadku, jest stabilne i stanowi lepszy wybór dla list wiązanych oraz sortowania zewnętrznego. Quicksort ma średnią złożoność O(n log n), ale w najgorszym przypadku O(n²), działa w miejscu (O(log n) pamięci stosu) i często jest w praktyce szybszy dzięki efektywnemu wykorzystaniu pamięci podręcznej dla tablic. Wbudowane sortowanie Pythona używa algorytmu Timsort (odmiany sortowania przez scalanie) — to zawsze właściwy wybór domyślny.
# Head-to-head complexity comparison:
# Algorithm | Best | Avg | Worst | Space | Stable
# Bubble sort | O(n) | O(n^2) | O(n^2) | O(1) | Yes
# Insertion sort| O(n) | O(n^2) | O(n^2) | O(1) | Yes
# Merge sort | O(nlogn)| O(nlogn)| O(nlogn)| O(n) | Yes
# Quick sort | O(nlogn)| O(nlogn)| O(n^2) | O(logn)| No
# Heap sort | O(nlogn)| O(nlogn)| O(nlogn)| O(1) | No
print('Merge sort: stable, O(n log n) guaranteed, O(n) space')Sortowanie zewnętrzne: sortowanie przez scalanie na dużą skalę
Sortowanie przez scalanie jest algorytmem używanym do sortowania zewnętrznego (sortowania danych, które nie mieszczą się w pamięci RAM). Dane są odczytywane fragmentami, każdy fragment jest sortowany w pamięci, a następnie fragmenty są scalane z dysku. Podczas scalania odczytywany jest po jednym elemencie z każdego posortowanego przebiegu, dzięki czemu jednocześnie w pamięci przechowuje się tylko O(k) elementów (po jednym na przebieg). Dlatego sortowanie przez scalanie jest używane w bazach danych, Hadoop MapReduce oraz klasycznych algorytmach sortowania na taśmach.
# Simulated external sort: sort in chunks then merge
def external_sort(data, chunk_size):
chunks = []
for i in range(0, len(data), chunk_size):
chunk = sorted(data[i:i+chunk_size]) # sort in-memory
chunks.append(chunk)
print(f'Created {len(chunks)} sorted chunks')
# Merge all chunks
import heapq
heap = [(c[0], i, 0) for i, c in enumerate(chunks) if c]
heapq.heapify(heap)
result = []
while heap:
val, ci, ei = heapq.heappop(heap)
result.append(val)
if ei + 1 < len(chunks[ci]):
heapq.heappush(heap, (chunks[ci][ei+1], ci, ei+1))
return result
print(external_sort(list(range(20,0,-1)), 5)[:10])Podsumowanie sortowania przez scalanie i wskazówki dotyczące rozmów kwalifikacyjnych
Podczas rozmów kwalifikacyjnych przejrzysta implementacja sortowania przez scalanie pokazuje zrozumienie rekurencji, etapu scalania oraz strategii dziel i zwyciężaj. Częste pytania dodatkowe:
- Dlaczego O(n log n), a nie O(n²)? (log n poziomów × n pracy na poziom)
- Czy algorytm jest stabilny? (Tak, w scalaniu należy użyć <=)
- Ile pamięci wykorzystuje? (O(n) pamięci pomocniczej + O(log n) stosu)
- Czy można wykonać go iteracyjnie? (Tak, za pomocą sortowania przez scalanie oddolnego)
- Jak zastosować go do listy wiązanej? (Łatwiej niż do tablicy — brak kosztu wycinania fragmentów O(n); do znalezienia punktu środkowego należy użyć metody wolnego i szybkiego wskaźnika)
# One-shot merge sort for interview clarity:
def ms(a):
if len(a) <= 1: return a
m = len(a) // 2
l, r, res, i, j = ms(a[:m]), ms(a[m:]), [], 0, 0
while i < len(l) and j < len(r):
if l[i] <= r[j]: res.append(l[i]); i+=1
else: res.append(r[j]); j+=1
return res + l[i:] + r[j:]
print(ms([5,2,4,6,1,3])) # [1,2,3,4,5,6]Szybki test
Sprawdź swoją wiedzę z koncepcji kursu Data Structures & Algorithms — Coding Interview Prep omówionych w tej lekcji.
Podsumowanie lekcji
W tej lekcji nauczył(a) się Pan/Pani, że: sortowanie przez scalanie dzieli tablicę w punkcie środkowym, rekurencyjnie sortuje każdą połowę, a następnie scala obie posortowane połowy w czasie O(n) — co daje łączny czas O(n log n) na przestrzeni log n poziomów rekurencji, etap scalania używa <=, aby w przypadku remisu wybrać element z lewej strony, gwarantując stabilność, a także że sortowanie przez scalanie jest algorytmem z wyboru dla list wiązanych, sortowania zewnętrznego oraz sytuacji, w których wymagana jest stabilność — natomiast quicksort preferuje się dla tablic przechowywanych w pamięci, gdy ilość pamięci jest ograniczona. Następnie zaimplementujemy quicksort i omówimy strategie wyboru pivota.
Często zadawane pytania
Czy lekcja „Sortowanie przez scalanie: podziel, posortuj, scal” jest bezpłatna?
Tak — pełny tekst „Sortowanie przez scalanie: podziel, posortuj, scal” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Sortowanie przez scalanie: podziel, posortuj, scal”?
Zaimplementują Państwo rekurencyjne sortowanie przez scalanie, prześledzą drzewo algorytmu dziel i zwyciężaj oraz wyjaśnią, dlaczego we wszystkich przypadkach gwarantuje ono O(n log n). Ćwiczysz Coding Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć Coding Interview Prep?
Nie wymagamy żadnego doświadczenia. Coding Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 2 z 4.
Ile czasu zajmuje lekcja „Sortowanie przez scalanie: podziel, posortuj, scal”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji Coding Interview Prep?
Tak. Każda lekcja Coding Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Sortowanie bąbelkowe i przez wstawianie
- Sortowanie przez scalanie: podziel, posortuj, scal
- Quick Sort i wybór pivota
- Sortowania nieporównawcze i sort() w Pythonie