Sortowanie przez scalanie
Sortowanie przez scalanie to interaktywny eksperyment z aplikacji Algorytmy w akcji – darmowej symulacji ze StudyFi Lab, która działa bezpośrednio w przeglądarce.
Sortowanie przez scalanie dzieli tablicę na połowy, sortuje każdą w ten sam sposób (rekurencja), a potem scala dwie posortowane połowy: zawsze bierze mniejszy z dwóch pierwszych elementów. Dzielenie na pół daje log₂ n poziomów, a każdy poziom przetwarza wszystkie n elementów, więc złożoność czasowa to zawsze O(n log n). Przy remisie bierze element z lewej, dlatego jest stabilne.
Spróbuj: Spróbuj odwróconej, a potem prawie posortowanej tablicy tej samej wielkości. Liczba porównań prawie się nie zmienia — kolejność danych ma niewielkie znaczenie.
Najczęstsze pytania
Co pokazuje eksperyment „Sortowanie przez scalanie”?
Sortowanie przez scalanie dzieli tablicę na połowy, sortuje każdą w ten sam sposób (rekurencja), a potem scala dwie posortowane połowy: zawsze bierze mniejszy z dwóch pierwszych elementów. Dzielenie na pół daje log₂ n poziomów, a każdy poziom przetwarza wszystkie n elementów, więc złożoność czasowa to zawsze O(n log n). Przy remisie bierze element z lewej, dlatego jest stabilne.
Jak wypróbować „Sortowanie przez scalanie”?
Spróbuj odwróconej, a potem prawie posortowanej tablicy tej samej wielkości. Liczba porównań prawie się nie zmienia — kolejność danych ma niewielkie znaczenie.
Uczysz się do sprawdzianu?
Wgraj swoje notatki, a StudyFi zrobi z nich fiszki, testy i podcasty.