Sortowanie przez podział MERGE

0

Witam serdecznie.
Nigdzie nie mogę znaleźć odpowiedzi na moje pytanie, tak więc zakładam nowy temat.
Na zajęciach z ASD mieliśmy zadane napisać program, który sortuje tablicę przez podział.
Jednak program ten nie miał dzielić tablicy na dwie części, a na trzy.
Program napisałem, nie było z tym większego problemu.

Mianowicie mam jeszcze odpowiedzieć na pytanie, czy sortowanie z podziałem na trzy części jest lepsze czy gorsze niż sortowanie z podziałem na dwie części? Czy też oba są równie dobre?

Proszę o odpowiedz na pytanie i uzasadnienie.
Będę bardzo wdzięczny za pomoc.
Pozdrawiam

0

Ilość poziomów scalania jest log2(3)=1,58 razy mniejsza przy dzieleniu na 3, ale w scalaniu masz więcej porównań (2 vs 1, oszacowanie gdy porównanie elementów jest drogie, np. string i przypadek negatywny, zależy od implementacji), żeby znaleźć liczbę najmniejszą z trzech, ilość kopiowań zależy od ilości poziomów, więc będzie mniejsza dla dzielenia na 3. Najlepiej po prostu sprawdzić czas dla powiedzmy 1e5, 1e6, 1e7, 1e8 losowych liczb, walnąć wykresik logarytmiczny, złożoność jest taka sama, więc będzie widać która implementacja jest szybsza.

0

Ja mam wyniki z poprzedniego roku i okazało się, że Merge2 jest wydajniejszy, taka odpowiedz tolerował Kaczmarek. Więc Merge2.

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0