Problema saptamanii - Mediana pe disc

Cosmin Negruseri
28 iulie 2009

Cum numarul de rezolvari atat bune cat si rele a fost mare la problema anterioara, va mai zic o problema cu statistici de ordine pe care am auzit-o de la Mihai Patrascu.

Se dau n numere intregi scrise pe disc. Se cere sa se detemine mediana lor in timp O(n), citind fiecare numar de pe disc de O(1) ori si folosind O(sqrt(n)) memorie totala. Mediana unui sir de numere cu n elemente e elementul de pe pozitia n/2 din sirul rezultat in urma sortarii sirului initial.