Motywacja

Merge Sort dzieli problem na mniejsze podproblemy, rozwiązuje każdy z nich i łączy wyniki. Ten etap łączenia, czyli scalanie dwóch już posortowanych list, stanowi sedno algorytmu.

Dlaczego warto poznać Merge Sort?

• Szybki i przewidywalny: działa w czasie O(n log n) w najlepszym, przeciętnym i najgorszym przypadku.
• Stabilny: równe elementy zachowują swój pierwotny porządek względny.
• Świetny w przypadku dużych zbiorów danych: sprawdza się, gdy dane nie mieszczą się w pamięci (sortowanie zewnętrzne), oraz w przypadku list wiązanych.
• Dziel i zwyciężaj: uczy wzorca stosowanego w wielu zaawansowanych algorytmach.