AiSD -- mergesort w miejscu, zadanie domowe

Zadanie

Zaimplementuj (w Pascalu/C/C++) algorytm MergeSort używający dodatkowo O(1) pamięci. Np. stosując algorytm podany na ćwiczeniach, lub opisany przez Knuth’a.

Wejście

Pierwszy wiersz standardowego wejścia zawiera liczbę całkowitą n -- rozmiar ciągu do posortowania, 1 < n <= 1000000. W kolejnych n wierszach zapisano liczby do posortowania, każda w osobnym wierszu. Każda z liczb jest z zakresu 0..1000000000.

Wyjście

Na standardowym wyjściu należy zapisać n wierszy -- posortowany ciąg. Każda z liczb powinna być zapisana w osobnym wierszu.

Przykład

Dla danych:

4
3
1000
2
100

prawidłową odpowiedzią jest:

2
3
100
1000

Ocenianie

Rozwiązania będą oceniane na zestawie danych testowych. Rozwiązania niesamodzielne nie będą rozpatrywane. Za W PEŁNI PRAWIDŁOWE rozwiązanie można otrzymać bonus w postaci +20% punktów do 1. kolokwium (prawdopodobnie +4-5 punktów).

Zgłaszanie rozwiązań

Rozwiązania należy nadsyłać pocztą na adres walen@mimuw.edu.pl. Ostateczny termin zgłaszania rozwiązań mija 7.11.2003 o godzinie 12:00. Zgłoszenie powinno zawierać:

• imię i nazwisko,
• nr indeksu,
• kod źródłowy z rozwiązaniem (Pascal/C/C++).