Algorytm quicksort

Question

Mam pewne pytanie.

Znalazłem w internecie taki schemat sortowania przez scalanie. Otóż zastanawiam się czy quicksort wykorzystuje scalanie dwóch ciągów uporządkowanych. W quicksort występuje "dzielenie" problemu na mniejsze. Ale czy quicksort wykorzystuje scalanie posortowanych ciągów?

Answer 1

Quicksort podobnie jak merge sort rozbija tablicę na coraz mniejsze części, lecz nie wykonuje on potem scalania. Jak zapewne wiesz, quicksort działa tak, że znajdujesz sobie pivot i względem niego sortujesz pewną część tablicy i potem znowu powtarzasz to rekurencyjnie dla części na prawo od pivota i na lewo. Musisz zauważyć, że gdy skończymy rozważać jakiś pivot, to będzie się on już znajdował na swojej właściwej pozycji w posortowanym ciągu. Czyli jak rozważymy każdy element jako pivot to nie ma już potrzeby scalać tego wszystkiego.