[Algorytmy] rozdzielenie tablicy na dwie względem mediany

[gmore]

Mamy tablicę parzystej długości - \(\displaystyle{ A[2n]}\) - wypełnioną liczbami całkowitymi. Chcemy ją tak przestawić, by zachodziło \(\displaystyle{ A[k] \le A[j]}\) dla dowolnych \(\displaystyle{ k\le n ;j>n}\) (używam tu konwencji, że tablicę numerujemy poczynając od jedynki). Jak to zrobić w \(\displaystyle{ O(n)}\)? Wiadomo, że dla \(\displaystyle{ O(n\log (n))}\) wystarczy sobie posortować.

[Afish]

Algorytm magicznych piątek.