h3. $O(N logN)$ la Nave & adaptabila sa obtina $O(N)$ la Ordonare

Punctul culminant al postarii - si motivul principal pentru care ea exista - este solutia la Nave a lui ==user(user="retrograd" type="tiny")==. Tin sa mentionez ca este foarte diferita de toate celelalte. Pentru a va ghida spre patrunderea ei, am pregatit o serie de hinturi ('1':nave-lucian-hint1, '2':nave-lucian-hint2, '3':nave-lucian-hint3, '4':nave-lucian-hint4, '5':nave-lucian-hint5, '6':nave-lucian-hint6), 'un mic articol':nave-prea-usor care merge mana in mana cu indiciile, precum si doua surse foarte asemanatoare, bine comentate si codate cat mai clar. 'Prima':job_detail/2653120?action=view-source mi se pare mai intuitiva, iar 'a doua':job_detail/2653119?action=view-source (recomand "text-compare.com":https://text-compare.com/) urmeaza ceva mai indeaproape 'implementarea origina{*r*}a':job_detail/2651731?action=view-source a lui Lucian.

Punctul culminant al postarii - si motivul principal pentru care ea exista - este solutia la Nave a lui ==user(user="retrograd" type="tiny")==. Tin sa mentionez ca este foarte diferita de toate celelalte.
 
Mai intai, vom face o transformare a sirului dat, intr-o reprezentare echivalenta, si anume un sir de $2N$ frecvente, $input[i]$ = numarul de valori egale cu $i$ din sirul dat.
 
Pentru a va ghida spre patrunderea ei, am pregatit o serie de hinturi ('1':nave-lucian-hint1, '2':nave-lucian-hint2, '3':nave-lucian-hint3, '4':nave-lucian-hint4, '5':nave-lucian-hint5, '6':nave-lucian-hint6), 'un mic articol':nave-prea-usor care merge mana in mana cu indiciile, precum si doua surse foarte asemanatoare, bine comentate si codate cat mai clar. 'Prima':job_detail/2653120?action=view-source mi se pare mai intuitiva, iar 'a doua':job_detail/2653119?action=view-source (recomand "text-compare.com":https://text-compare.com/) urmeaza ceva mai indeaproape 'implementarea origina{*r*}a':job_detail/2651731?action=view-source a lui Lucian.

*Odata ce intelegeti solutia aceasta*, puteti rezolva (si o puteti privi ca pe o tema) si problema Ordonare, doar ca in timp liniar (reminder: dupa ce faceti reducerea!). In caz ca nu-i dati de cap, iata un 'indiciu':de-la-nave-la-ordonare. Avantajul aici e ca multe detalii la care trebuia sa aveti grija la Nave nu mai conteaza, deci sursa e mai lejer de scris.