Prezentare generală a sortării prin interclasare (îmbinare)

Deoarece folosim divide et impera pentru sortare, trebuie să decidem cum arată subproblemele noastre. Problema inițială este sortarea unui întreg vector. Să spunem că o subproblemă este sortarea unui subșir din vector. Concret, ne vom gândi la o subproblemă ca fiind sortarea subșirului care începe de la poziția $p$‍ și se termină la poziția $r$‍. Este convenabil să alegem o notație pentru un subșir, așa că vom scrie array[p..r] pentru un subșir al vectorului array. Trebuie să ai în vedere că scrierea cu „două puncte” nu face parte din JavaScript; o folosim doar pentru a descrie algoritmul, nu pentru a scrie cod. Pe baza notației noastre, pentru un vector cu $n$‍ elemente, putem spune că problema inițială este sortarea lui array[0..n-1].

Iată cum sortarea prin interclasare folosește divide et impera:

Avem nevoie de un caz elementar (de bază). Cazul elementar este un subșir ce conține mai puțin de două elemente, adică are proprietatea $p\ge r$‍, din moment ce un subșir cu niciun element sau cu un singur element este deja sortat. Așadar, vom aplica divide et impera doar atunci când $p<r$‍.

Hai să vedem un exemplu. Să începem cu un vector array care are elementele [14, 7, 3, 12, 9, 11, 6, 2], iar subșirul său inițial este chiar întregul vector, array[0..7] ($p=0$‍ și $r=7$‍). Acest subșir are cel puțin două elemente, deci nu reprezintă un caz elementar.

Cum a fost sortat subșirul array[0..3]? În același mod. Are mai mult de două elemente, deci nu reprezintă un caz elementar. Cu $p=0$‍ și $r=3$‍, găsim $q=1$‍, sortăm recursiv array[0..1] ([14, 7]) și array[2..3] ([3, 12]) și obținem array[0..3] ce conține [7, 14, 3, 12], apoi interclasăm prima jumătate cu cea de-a doua și rezultă [3, 7, 12, 14].

Cum a fost sortat subșirul array[0..1]? Cu $p=0$‍ și $r=1$‍, găsim $q=0$‍, sortăm recursiv array[0..0] ([14]) și array[1..1] ([7]) și obținem array[0..1] ce conține tot [14, 7], apoi interclasăm prima jumătate cu cea de-a doua și rezultă [7, 14].

Subșirurile array[0..0] și array[1..1] sunt cazuri elementare (de bază), din moment ce fiecare conține mai puțin de două elemente. Iată cum se desfășoară întregul algoritm al sortării prin interclasare:

Majoritatea pașilor sortării prin interclasare sunt simpli. Poți verifica ușor cazul elementar (de bază). Găsirea mijlocului $q$‍ în etapa divide (de împărțire) se face cu ușurință. Trebuie să faci două apeluri recursive în etapa de rezolvare. Etapa de combinare în care trebuie să interclasezi două subșiruri sortate este cea mai solicitantă.

În următoarea provocare, te vei concentra pe implementarea algoritmului general de sortare prin interclasare, pentru a fi sigur că înțelegi cum să aplici divide et impera recursiv. Apoi vom analiza mai atent modul în care putem interclasa în mod eficient două subșiruri sortate şi vei implementa și acest algoritm într-o provocare ulterioară.

Acest conținut este o colaborare a profesorilor Thomas Cormen și Devin Balkcom, de la Dartmouth Computer Science, cu echipa de elaborare a curriculumului de informatică de la Khan Academy. Conținutul este licențiat CC-BY-NC-SA.