Jak scalić tablicę posortowaną w miejscu

0

Chcę napisać program w Javie, który sortuje tablicę przez scalanie iteracyjnie, oraz wykonuje scalanie dwóch podtablich posortowanych w miejscu, czyli bez dodatkowej tablicy. Mam problem z funkcją scalającą. Próbowałem już na wiele sposobów. Jak to zrobić.

0

Te sposoby są bardzo skomplikowane. Nie da się tego zrobić prościej?

1

OK. Algo jest rekurencyjni i ma złożoność O(n lg n) - samo merge'owanie. Stad cały mergesort będzie miał O(n lg n lg n).

Na wejściu jest ciąg który składa się z dwóch rosnących podciągów.
Pomysł polega na tym, że bierzemy środkowy element z dłuższego i znajdujemy go w krótszym. Potem robimy reverse'a na ciągu elementów pomiędzy tymi dwoma elementami. Wtedy powstaje ciąg który jest najpierw rosnący, później malejący, później rosnący i później malejący. Ciągu malejące odwracamy. Powstają cztery rosnące podciągi, z tym że dwa pierwsze ciągi mają wszystkie elementy mniejsze niż w ostatnich dwóch. Należy więc rekurencyjnie zrobić merge na dwóch parach podciągów: tych z przodu i tych z tyłu.

Rozmiar największego podproblemu to maksymalnie 75% rozmiaru wejścia (na danym poziomie rekurencji), więc poziomów rekurencji jest logarytmiczna ilość.

Przy zastosowaniu ostrożności da się zaimplementować algorytm tak by działał przy powtarzających się elementach.

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