Problema saptamanii - Interclasare

Cosmin Negruseri
08 august 2010

Revenim dupa o pauza considerabila cu problema saptamanii:

Se da un sir A de n + m numere intregi. Numerele de la 1 la n sunt in ordine crescatoare si numerele de la n + 1 la n + m sunt si ele in ordine crescatoare. Se cere sa se sorteze sirul in ordine crescatoare. Algoritmul trebuie sa foloseasca memorie suplimentara constanta, ordinea numerelor sa fie stabila, adica oricare doua numere egale din sir sa nu apara in aceiasi ordine dupa ce sirul a fost sortat, iar complexitatea algoritmului trebuie sa fie mai buna de O(n^2).