Algoritmul de sortare prin interclasare a fost inventat de John von Neumann în 1945. Merge bine pe liste. Față de algoritmul de sortare rapidă are o complexitate mai mică în timp (O(nlog₂n)), dar mai mare în spațiu (își creează spații de memorie temporare). Păstrează ordinea relativă a elementelor având aceeași valoare a cheii de sortare.
10 0 -1 -3 1 -4 9 3 -1 -4 3 -4
Am apelat în main() MergeSort(v,1,12), cu
st=1 și dr=12. 1<12=>st<dr=>m=6=>MergeSort(v,st,m)=MergeSort(v,1,6)=>dr=6.
1<6=>st<dr=>m=3=>MergeSort(v,st,m)=MergeSort(v,1,3)=>dr=3.
1<3=>st<dr=>m=2=>MergeSort(v,st,m)=MergeSort(v,1,2)=>dr=1. (1=1=>st=dr).
Încheiem apelul MergeSort(v,1,1)=>(ne întoarcem cu un apel, la MergeSort(v,1,2))=>MergeSort(v,m+1,dr)=MergeSort(v,1+1,2)=MergeSort(v,2,2)=>st=2.
(2=2=>st=dr). Încheiem apelul MergeSort(v,2,2)=>(ne întoarcem cu un apel,
la MergeSort(v,1,2))=>i=st=1, j=m+1=1+1=2, k=0. (1=1=>i≤m și 2=2=>j≤dr).
Intrăm în primul while (s-au respectat condițiile). 10>0=>v[i]≥v[j]=>(intrăm
în else)=>tmp[++k]=tmp[1]=v[2]=0. (1=1=>i≤m și 3>2=>j>dr). Ieșim
din primul while (nu s-a respectat a doua condiție). (1=1=>i≤m). Intrăm în
al doilea while (s-a respectat condiția). tmp[++k]=tmp[2]=v[1]=10.
(2>1=>i>m). Ieșim din al doilea while (nu s-a respectat condiția). (3>2=>j>dr).
Nu intrăm în al treilea while (nu s-a respectat condiția). Intrăm în for. i=st=1,
j=1. (1<2=>i≤dr). Continuăm for-ul (s-a respectat condiția).
v[i]=v[1]=tmp[j]=tmp[1]=0. Postincrementăm i, și pe urmă j. (2=2=>i≤dr).
Continuăm for-ul (s-a respectat condiția). v[i]=v[2]=tmp[j]=tmp[2]=10. Postincrementăm
i, și pe urmă j. (3>2=>i>dr). Ieșim din for (nu s-a respectat condiția).
0 10 -1 -3 1 -4 9 3 -1 -4 3 -4
Am încheiat apelul
MergeSort(v,1,2)=>(ne întoarcem cu un apel, la MergeSort(v,1,3))=>MergeSort(v,m+1,dr)=MergeSort(v,2+1,3)=MergeSort(v,3,3)=>st=3.
(3=3=>st=dr). Încheiem apelul MergeSort(v,3,3)=>(ne întoarcem cu un apel,
la MergeSort(v,1,3))=>i=st=1, j=m+1=2+1=3, k=0. (1<2=>i≤m și 3=3=>j≤dr).
Intrăm în primul while (s-au respectat condițiile). 0>-1=>v[i]≥v[j]=>(intrăm
în else)=>tmp[++k]=tmp[1]=v[3]=-1. (1<2=>i≤m și 4>3=>j>dr). Ieșim
din primul while (nu s-a respectat a doua condiție). (1<2=>i≤m). Intrăm
în al doilea while (s-a respectat condiția). tmp[++k]=tmp[2]=v[1]=0. (2=2=>i≤m).
Continuăm while-ul (s-a respectat condiția). tmp[++k]=tmp[3]=v[2]=10.
(3>2=>i>m). Ieșim din al doilea while (nu s-a respectat condiția). Nu
intrăm în al treilea while (nu s-a respectat condiția). Intrăm în for. i=st=1,
j=3. Postincrementăm i, și pe urmă j. (1<3=>i≤m). Continuăm for-ul (s-a
respectat condiția). v[i]=v[1]=tmp[j]=tmp[1]=-1. Postincrementăm i, și pe urmă
j. (2<3=>i≤m). Continuăm for-ul (s-a respectat condiția).
v[i]=v[2]=tmp[j]=tmp[2]=0. Postincrementăm i, și pe urmă j. (3=3=>i≤m). Continuăm
for-ul (s-a respectat condiția). v[i]=v[3]=tmp[j]=tmp[3]=10. Postincrementăm i,
și pe urmă j. (4>3=>i>m). Ieșim din for (nu s-a respectat condiția).
-1 0 10 -3 1 -4 9 3 -1 -4 3 -4
Am încheiat apelul MergeSort(v,1,3)=>(ne
întoarcem cu un apel, la MergeSort(v,1,6))=>MergeSort(v,m+1,dr)=MergeSort(v,3+1,6)=MergeSort(v,4,6)=>st=4.
4<6=>st<dr=>m=5=> MergeSort(v,st,m)=MergeSort(v,4,5)=>m=4=>MergeSort(v,st,m)=MergeSort(v,4,4)=>dr=4.
(4=4=>st=dr). Încheiem apelul MergeSort(v,4,4)=>(ne întoarcem cu un apel,
la MergeSort(v,4,5))=>MergeSort(v,m+1,dr)=MergeSort(v,4+1,5)=MergeSort(v,5,5).
(5=5=>st=dr). Încheiem apelul MergeSort(v,5,5)=>(ne întoarcem cu un apel,
la MergeSort(v,4,5))=>i=st=4, j=m+1=4+1=5, k=0. (4=4=>i≤m și 5=5=>j≤dr).
Intrăm în primul while (s-au respectat condițiile). -3<1=>v[i]<v[j]=>(intrăm
în if)=>tmp[++k]=tmp[1]=v[4]=-3. (5>4=>i>m și 5=5=>j≤dr). Ieșim
din primul while (nu s-a respectat prima condiție). (5>4=>i>m). Nu
intrăm în al doilea while (nu s-a respectat condiția). (5=5=>j≤dr). Intrăm
în al treilea while (s-a respectat condiția). tmp[++k]=tmp[2]=v[5]=1.
(6>5=>j>dr). Ieșim din al treilea while (nu s-a respectat condiția). Intrăm
în for. i=st=4, j=1. (4<5=>i≤dr). Continuăm for-ul (s-a respectat
condiția). v[i]=v[4]=tmp[j]=tmp[1]=-3. Postincrementăm i, și pe urmă j. (5=5=>i≤dr).
Continuăm for-ul (s-a respectat condiția). v[i]=v[5]=tmp[j]=tmp[2]=1.
Postincrementăm i, și pe urmă j. (6>5=>i>dr). Ieșim din for (nu s-a
respectat condiția).
-1 0 10 -3 1 -4 9 3 -1 -4 3 -4
Am încheiat apelul
MergeSort(v,4,5)=>(ne întoarcem cu un apel, la MergeSort(v,4,6))=>MergeSort(v,m+1,dr)=MergeSort(v,5+1,6)=MergeSort(v,6,6)=>st=6.
(6=6=>st=dr). Încheiem apelul MergeSort(v,6,6)=>(ne întoarcem cu un apel,
la MergeSort(v,4,6))=>i=st=4, j=m+1=5+1=6, k=0. (4<5=>i≤m și 6=6=>j≤dr).
Intrăm în primul while (s-au respectat condițiile). -3>-4=>v[i]≥v[j]=>(intrăm
în else)=>tmp[++k]=tmp[1]=v[6]=-4. (4<5=>i≤m și 7>6=>j>dr).
Ieșim din primul while (nu s-a respectat a doua condiție). (4<5=>i≤m).
Intrăm în al doilea while (s-a respectat condiția). tmp[++k]=tmp[2]=v[4]=-3.
(5=5=>i≤m). Continuăm while-ul (s-a respectat condiția). tmp[++k]=tmp[3]=v[5]=1.
(3>2=>i>m). Ieșim din al doilea while (nu s-a respectat condiția). (7>6=>j>dr).
Nu intrăm în al treilea while (nu s-a respectat condiția). Intrăm în for.
i=st=4, j=1. (4<6=>i≤dr). Continuăm for-ul (s-a respectat condiția). v[i]=v[4]=tmp[j]=tmp[1]=-4.
Postincrementăm i, și pe urmă j. (5<6=>i≤dr). Continuăm for-ul (s-a
respectat condiția). v[i]=v[5]=tmp[j]=tmp[2]=-3. Postincrementăm i, și pe urmă
j. (6=6=>i≤dr). Continuăm for-ul (s-a respectat condiția). v[i]=v[6]=tmp[j]=tmp[3]=1.
Postincrementăm i, și pe urmă j. (7>6=>i>dr). Ieșim din for (nu s-a
respectat condiția).
-1 0 10 -4 -3 1 9 3 -1 -4 3 -4
Am încheiat apelul MergeSort(v,4,6)=>(ne
întoarcem cu un apel, la MergeSort(v,1,6))=>i=st=1, j=m+1=3+1=4, k=0. (1<3=>i≤m
și 4<6=>j≤dr). Intrăm în primul while (s-au respectat condițiile). -1>-4=>v[i]≥v[j]=>(intrăm
în else)=>tmp[++k]=tmp[1]=v[4]=-4. (1<3=>i≤m și 5<6=>j≤dr). Continuăm
while-ul (s-au respectat condițiile). -1>-3=>v[i]≥v[j]=>(intrăm în else)=>tmp[++k]=tmp[2]=v[5]=-3.
(1<3=>i≤m și 6=6=>j≤dr). Continuăm while-ul (s-au respectat condițiile).
-1<1=>v[i]<v[j]=>(intrăm în if)=>tmp[++k]=tmp[3]=v[1]=-1. (2<3=>i≤m
și 6=6=>j≤dr). Continuăm while-ul (s-au respectat condițiile). 0<1=>v[i]<v[j]=>(intrăm
în if)=>tmp[++k]=tmp[4]=v[2]=0. (3=3=>i≤m și 6=6=>j≤dr). Continuăm
while-ul (s-au respectat condițiile). 10>1=>v[i]≥v[j]=>(intrăm în
else)=>tmp[++k]=tmp[5]=v[6]=1. (3=3=>i≤m și 7>6=>j>dr). Ieșim
din primul while (nu s-a respectat a doua condiție). (3=3=>i≤m). Intrăm în
al doilea while (s-a respectat condiția). tmp[++k]=tmp[6]=v[3]=10. (4>3=>i>m).
Ieșim din al doilea while (nu s-a respectat condiția). (7>6=>j>dr). Nu
intrăm în al treilea while (nu s-a respectat condiția). Intrăm în for. i=st=1,
j=1. (1<6=>i≤dr). Continuăm for-ul (s-a respectat condiția). v[i]=v[1]=tmp[j]=tmp[1]=-4.
Postincrementăm i, și pe urmă j. (2<6=>i≤dr). Continuăm for-ul (s-a
respectat condiția). v[i]=v[2]=tmp[j]=tmp[2]=-3. Postincrementăm i, și pe urmă
j. (3<6=>i≤dr). Continuăm for-ul (s-a respectat condiția).
v[i]=v[3]=tmp[j]=tmp[3]=-1. Postincrementăm i, și pe urmă j. (4<6=>i≤dr).
Continuăm for-ul (s-a respectat condiția). v[i]=v[4]=tmp[j]=tmp[4]=0. Postincrementăm
i, și pe urmă j. (5<6=>i≤dr). Continuăm for-ul (s-a respectat condiția). v[i]=v[5]=tmp[j]=tmp[5]=1.
Postincrementăm i, și pe urmă j. (6=6=>i≤dr). Continuăm for-ul (s-a
respectat condiția). v[i]=v[6]=tmp[j]=tmp[6]=10. Postincrementăm i, și pe urmă
j. (7>6=>i>dr). Ieșim din for (nu s-a respectat condiția).
-4 -3 -1 0 1 10 9 3 -1 -4 3 -4
Am încheiat apelul MergeSort(v,1,6)=>(ne
întoarcem cu un apel, la MergeSort(v,1,12))=>MergeSort(v,m+1,dr)=MergeSort(v,6+1,12)=MergeSort(v,7,12)=>st=7.
7<12=>st<dr=>m=9=>MergeSort(v,st,m)=MergeSort(v,7,9)=>dr=9. 7<9=>st<dr=>m=8=>MergeSort(v,st,m)=MergeSort(v,7,8)=>dr=8.
7<8=>st<dr=>m=7=>MergeSort(v,st,m)=MergeSort(v,7,7)=>dr=7.
(7=7=>st=dr). Încheiem apelul MergeSort(v,7,7)=>(ne întoarcem cu un apel,
la MergeSort(v,7,8))=>MergeSort(v,m+1,dr)=MergeSort(v,7+1,8)=MergeSort(v,8,8)=>st=8.
(8=8=>st=dr). Încheiem apelul MergeSort(v,8,8)=>(ne întoarcem cu un apel,
la MergeSort(v,7,8))=>i=st=7, j=m+1=7+1=8, k=0. (7=7=>i≤m și 8=8=>j≤dr).
Intrăm în primul while (s-au respectat condițiile). 9>3=>v[i]≥v[j]=>(intrăm
în else)=>tmp[++k]=tmp[1]=v[8]=3. (7=7=>i≤m și 9>8=>j>dr). Ieșim
din primul while (nu s-a respectat a doua condiție). (7=7=>i≤m). Intrăm în
al doilea while (s-a respectat condiția). tmp[++k]=tmp[2]=v[7]=9.
(8>7=>i>m). Ieșim din al doilea while (nu s-a respectat condiția). (9>8=>j>dr).
Nu intrăm în al treilea while (nu s-a respectat condiția). Intrăm în for.
i=st=7, j=1. (7<8=>i≤dr). Continuăm for-ul (s-a respectat condiția). v[i]=v[7]=tmp[j]=tmp[1]=3.
Postincrementăm i, și pe urmă j. (8=8=>i≤dr). Continuăm for-ul (s-a
respectat condiția). v[i]=v[8]=tmp[j]=tmp[2]=9. Postincrementăm i, și pe urmă
j. (9>8=>i>dr). Ieșim din for (nu s-a respectat condiția).
-4 -3 -1 0 1 10 3 9 -1 -4 3 -4
Am încheiat apelul
MergeSort(v,7,8)=>(ne întoarcem cu un apel, la MergeSort(v,7,9))=>MergeSort(v,m+1,dr)=MergeSort(v,8+1,9)=MergeSort(v,9,9)=>st=9.
(9=9=>st=dr). Încheiem apelul MergeSort(v,9,9)=>(ne întoarcem cu un apel,
la MergeSort(v,7,9))=>i=st=7, j=m+1=8+1=9, k=0. (7<8=>i≤m și 9=9=>j≤dr).
Intrăm în primul while (s-au respectat condițiile). 3>-1=>v[i]≥v[j]=>(intrăm
în else)=>tmp[++k]=tmp[1]=v[9]=-1. (7<8=>i≤m și 10>9=>j>dr).
Ieșim din primul while (nu s-a respectat a doua condiție). (7<8=>i≤m). Intrăm
în al doilea while (s-a respectat condiția). tmp[++k]=tmp[2]=v[7]=3. (8=8=>i≤m).
Continuăm while-ul (s-a respectat condiția). tmp[++k]=tmp[3]=v[8]=9.
(9>8=>i>m). Ieșim din al doilea while (nu s-a respectat condiția). (10>9=>j>dr).
Nu intrăm în al treilea while (nu s-a respectat condiția). Intrăm în for. i=st=7,
j=1. (7<9=>i≤dr). Continuăm for-ul (s-a respectat condiția). v[i]=v[7]=tmp[j]=tmp[1]=-1.
Postincrementăm i, și pe urmă j. (8<9=>i≤dr). Continuăm for-ul (s-a
respectat condiția). v[i]=v[8]=tmp[j]=tmp[2]=3. Postincrementăm i, și pe urmă
j. (9=9=>i≤dr). Continuăm for-ul (s-a respectat condiția). v[i]=v[9]=tmp[j]=tmp[3]=9.
Postincrementăm i, și pe urmă j. (10>9=>i>dr). Ieșim din for (nu s-a
respectat condiția).
-4 -3 -1 0 1 10 -1 3 9 -4 3 -4
Am încheiat apelul MergeSort(v,7,9)=>(ne
întoarcem cu un apel, la MergeSort(v,7,12))=>MergeSort(v,m+1,dr)=MergeSort(v,9+1,12)=MergeSort(v,10,12)=>st=10.
10<12=>st<dr=>m=11=>MergeSort(v,st,m)=MergeSort(v,10,11)=>dr=11.
10<11=>st<dr=>m=10=>MergeSort(v,st,m)=MergeSort(v,10,10)=>dr=10.
(10=10=>st=dr). Încheiem apelul MergeSort(v,10,10)=>(ne întoarcem cu un
apel, la MergeSort(v,10,11))=>i=st=10, j=m+1=10+1=11, k=0. (10=10=>i≤m și
11=11=>j≤dr). Intrăm în primul while (s-au respectat condițiile). -4<3=>v[i]<v[j]=>(intrăm
în if)=>tmp[++k]=tmp[1]=v[10]=-4. (11>10=>i>m și 11=11=>j≤dr).
Ieșim din primul while (nu s-a respectat prima condiție). (11>10=>i>m).
Nu intrăm în al doilea while (nu s-a respectat condiția). (11=11=>j≤dr). Intrăm
în al treilea while (s-a respectat condiția). tmp[++k]=tmp[2]=v[11]=3.
(12>11=>j>dr). Ieșim din al treilea while (nu s-a respectat condiția).
Intrăm în for. i=st=10, j=1. (10<11=>i≤dr). Continuăm for-ul (s-a
respectat condiția). v[i]=v[10]=tmp[j]=tmp[1]=-4. Postincrementăm i, și pe urmă
j. (11=11=>i≤dr). Continuăm for-ul (s-a respectat condiția). v[i]=v[11]=tmp[j]=tmp[2]=3.
Postincrementăm i, și pe urmă j. (12>11=>i>dr). Ieșim din for (nu s-a
respectat condiția).
-4 -3 -1 0 1 10 -1 3 9 -4 3 -4
Am încheiat apelul MergeSort(v,10,11)=>(ne
întoarcem cu un apel, la MergeSort(v,10,12))=>MergeSort(v,m+1,dr)=MergeSort(v,11+1,12)=MergeSort(v,12,12)=>st=12.
(12=12=>st=dr). Încheiem apelul MergeSort(v,12,12)=>(ne întoarcem cu un apel,
la MergeSort(v,10,12))=>i=st=10, j=m+1=11+1=12, k=0. (10<11=>i≤m și 12=12=>j≤dr).
Intrăm în primul while (s-au respectat condițiile). -4=-4=>v[i]≥v[j]=>(intrăm
în else)=>tmp[++k]=tmp[1]=v[12]=-4. (10<11=>i≤m și
13>12=>j>dr). Ieșim din primul while (nu s-a respectat a doua
condiție). (10<11=>i≤m). Intrăm în al doilea while (s-a respectat
condiția). tmp[++k]=tmp[2]=v[10]=-4. (11=11=>i≤m). Continuăm while-ul (s-a
respectat condiția). tmp[++k]=tmp[3]=v[11]=3. (12>11=>i>m). Ieșim din
al doilea while (nu s-a respectat condiția). Intrăm în for. i=st=10, j=1. Postincrementăm
i, și pe urmă j. (10<12=>i≤dr). Continuăm for-ul (s-a respectat
condiția). v[i]=v[10]=tmp[j]=tmp[1]=-4. Postincrementăm i, și pe urmă j.
(11<12=>i≤dr). Continuăm for-ul (s-a respectat condiția).
v[i]=v[11]=tmp[j]=tmp[2]=-4. Postincrementăm i, și pe urmă j. (12=12=>i≤dr).
Continuăm for-ul (s-a respectat condiția). v[i]=v[12]=tmp[j]=tmp[3]=3. Postincrementăm
i, și pe urmă j. (13>12=>i>dr). Ieșim din for (nu s-a respectat condiția).
-4 -3 -1 0 1 10 -1 3 9 -4 -4 3
Am încheiat apelul MergeSort(v,10,12)=>(ne
întoarcem cu un apel, la MergeSort(v,7,12))=>i=st=7, j=m+1=9+1=10, k=0. (7<9=>i≤m
și 10<12=>j≤dr). Intrăm în primul while (s-au respectat condițiile). -1>-4=>v[i]≥v[j]=>(intrăm
în else)=>tmp[++k]=tmp[1]=v[10]=-4. (7<9=>i≤m și 11<12=>j≤dr).
Continuăm while-ul (s-au respectat condițiile).
-1>-4=>v[i]≥v[j]=>(intrăm în else)=>tmp[++k]=tmp[2]=v[11]=-4. (7<9=>i≤m
și 12=12=>j≤dr). Continuăm while-ul (s-au respectat condițiile).
-1<3=>v[i]<v[j]=>(intrăm în if)=>tmp[++k]=tmp[3]=v[7]=-1.
(8<9=>i≤m și 12=12=>j≤dr). Continuăm while-ul (s-au respectat condițiile).
3=3=>v[i]≥v[j]=>(intrăm în else)=>tmp[++k]=tmp[4]=v[12]=3.
(8<9=>i≤m și 13>12=>j>dr). Ieșim din primul while (nu s-a
respectat a doua condiție). (8<9=>i≤m). Intrăm în al doilea while (s-a
respectat condiția). tmp[++k]=tmp[5]=v[8]=3. (9=9=>i≤m). Continuăm while-ul
(s-a respectat condiția). tmp[++k]=tmp[6]=v[9]=9. (10>9=>i>m). Ieșim
din al doilea while (nu s-a respectat condiția). (13>12=>j>dr). Nu
intrăm în al treilea while (nu s-a respectat condiția). Intrăm în for. i=st=7,
j=1. (7<12=>i≤dr). Continuăm for-ul (s-a respectat condiția).
v[i]=v[7]=tmp[j]=tmp[1]=-4. Postincrementăm i, și pe urmă j. (8<12=>i≤dr).
Continuăm for-ul (s-a respectat condiția). v[i]=v[8]=tmp[j]=tmp[2]=-4.
Postincrementăm i, și pe urmă j. (9<12=>i≤dr). Continuăm for-ul (s-a
respectat condiția). v[i]=v[9]=tmp[j]=tmp[3]=-1. Postincrementăm i, și pe urmă
j. (10<12=>i≤dr). Continuăm for-ul (s-a respectat condiția).
v[i]=v[10]=tmp[j]=tmp[4]=3. Postincrementăm i, și pe urmă j. (11<12=>i≤dr).
Continuăm for-ul (s-a respectat condiția). v[i]=v[11]=tmp[j]=tmp[5]=3.
Postincrementăm i, și pe urmă j. (12=12=>i≤dr). Continuăm for-ul (s-a
respectat condiția). v[i]=v[12]=tmp[j]=tmp[6]=9. Postincrementăm i, și pe urmă
j. (13>12=>i>dr). Ieșim din for (nu s-a respectat condiția).
-4 -3 -1 0 1 10 -4 -4 -1 3 3 9
Am încheiat apelul
MergeSort(v,7,12)=>(ne întoarcem cu un apel, la MergeSort(v,1,12))=>i=st=1,
j=m+1=6+1=7, k=0. (1<6=>i≤m și 7<12=>j≤dr). Intrăm în primul while
(s-au respectat condițiile). -4=-4=>v[i]≥v[j]=>(intrăm în else)=>tmp[++k]=tmp[1]=v[7]=-4.
(1<6=>i≤m și 8<12=>j≤dr). Continuăm while-ul (s-au respectat condițiile).
-4=-4=>v[i]≥v[j]=>(intrăm în else)=>tmp[++k]=tmp[2]=v[8]=-4.
(1<6=>i≤m și 9<12=>j≤dr). Continuăm while-ul (s-au respectat
condițiile). -4<-1=>v[i]<v[j]=>(intrăm în if)=>tmp[++k]=tmp[3]=v[1]=-4.
(2<6=>i≤m și 9<12=>j≤dr). Continuăm while-ul (s-au respectat condițiile).
-3<-1=>v[i]<v[j]=>(intrăm în if)=>tmp[++k]=tmp[4]=v[2]=-3.
(3<6=>i≤m și 9<12=>j≤dr). Continuăm while-ul (s-au respectat
condițiile). -1=-1=>v[i]≥v[j]=>(intrăm în else)=>tmp[++k]=tmp[5]=v[9]=-1.
(3<6=>i≤m și 10<12=>j≤dr). Continuăm while-ul (s-au respectat
condițiile). -1<3=>v[i]<v[j]=>(intrăm în if)=>tmp[++k]=tmp[6]=v[3]=-1.
(4<6=>i≤m și 10<12=>j≤dr). Continuăm while-ul (s-au respectat
condițiile). 0<3=>v[i]<v[j]=>(intrăm în if)=>tmp[++k]=tmp[7]=v[4]=0.
(5<6=>i≤m și 10<12=>j≤dr). Continuăm while-ul (s-au respectat condițiile).
1<3=>v[i]<v[j]=>(intrăm în if)=>tmp[++k]=tmp[8]=v[5]=1. (6=6=>i≤m
și 10<12=>j≤dr). Continuăm while-ul (s-au respectat condițiile). 10>3=>v[i]≥v[j]=>(intrăm
în else)=>tmp[++k]=tmp[9]=v[10]=3. (6=6=>i≤m și 11<12=>j≤dr). Continuăm
while-ul (s-au respectat condițiile). 10>3=>v[i]≥v[j]=>(intrăm în else)=>tmp[++k]=tmp[10]=v[11]=3.
(6=6=>i≤m și 12=12=>j≤dr). Continuăm while-ul (s-au respectat condițiile).
10>9=>v[i]≥v[j]=>(intrăm în else)=>tmp[++k]=tmp[11]=v[12]=9.
(6=6=>i≤m și 13>12=>j>dr). Ieșim din primul while (nu s-a respectat
a doua condiție). (6=6=>i≤m). Intrăm în al doilea while (s-a respectat
condiția). tmp[++k]=tmp[12]=v[6]=10. (7>6=>j>dr). Ieșim din al doilea
while (nu s-a respectat condiția). (13>12=>j>dr). Nu intrăm în al
treilea while (nu s-a respectat condiția). Intrăm în for. i=st=1, j=1.
(1<12=>i≤dr). Continuăm for-ul (s-a respectat condiția). v[i]=v[1]=tmp[j]=tmp[1]=-4.
Postincrementăm i, și pe urmă j. (2<12=>i≤dr). Continuăm for-ul (s-a
respectat condiția). v[i]=v[2]=tmp[j]=tmp[2]=-4. Postincrementăm i, și pe urmă
j. (3<12=>i≤dr). Continuăm for-ul (s-a respectat condiția).
v[i]=v[3]=tmp[j]=tmp[3]=-4. Postincrementăm i, și pe urmă j. (4<12=>i≤dr).
Continuăm for-ul (s-a respectat condiția). v[i]=v[4]=tmp[j]=tmp[4]=-3.
Postincrementăm i, și pe urmă j. (5<12=>i≤dr). Continuăm for-ul (s-a
respectat condiția). v[i]=v[5]=tmp[j]=tmp[5]=-1. Postincrementăm i, și pe urmă
j. (6<12=>i≤dr). Continuăm for-ul (s-a respectat condiția).
v[i]=v[6]=tmp[j]=tmp[6]=-1. Postincrementăm i, și pe urmă j.
(7<12=>i≤dr). Continuăm for-ul (s-a respectat condiția).
v[i]=v[7]=tmp[j]=tmp[7]=0. Postincrementăm i, și pe urmă j. (8<12=>i≤dr).
Continuăm for-ul (s-a respectat condiția). v[i]=v[8]=tmp[j]=tmp[8]=1.
Postincrementăm i, și pe urmă j. (9<12=>i≤dr). Continuăm for-ul (s-a
respectat condiția). v[i]=v[9]=tmp[j]=tmp[9]=3. Postincrementăm i, și pe urmă
j. (10<12=>i≤dr). Continuăm for-ul (s-a respectat condiția).
v[i]=v[10]=tmp[j]=tmp[10]=3. Postincrementăm i, și pe urmă j.
(11<12=>i≤dr). Continuăm for-ul (s-a respectat condiția).
v[i]=v[11]=tmp[j]=tmp[11]=9. Postincrementăm i, și pe urmă j. (12=12=>i≤dr).
Continuăm for-ul (s-a respectat condiția). v[i]=v[12]=tmp[j]=tmp[12]=10.
Postincrementăm i, și pe urmă j. (13>12=>i>dr). Ieșim din for (nu s-a
respectat condiția). Am încheiat apelul MergeSort(v,1,12).
-4 -4 -4 -3 -1 -1 0 1 3 3 9 10
#include <iostream>
using namespace std;
int n,v[100005],tmp[100005];
void MergeSort(int st,int dr)
{
if (st<dr)
{
int m=(st+dr)/2;
MergeSort(st,m);
MergeSort(m+1,dr);
int i=st,j=m+1,k=0;
while (i<=m&&j<=dr)
if (v[i]<v[j])
tmp[++k]=v[i++];
else
tmp[++k]=v[j++];
while (i<=m)
tmp[++k]=v[i++];
while (j<=dr)
tmp[++k]=v[j++];
for (i=st,j=1;i<=dr;i++,j++)
v[i]=tmp[j];
}
}
int main()
{
int i;
cin>>n;
for (i=1;i<=n;++i)
cin>>v[i];
MergeSort(1,n);
for (i=1;i<=n;++i)
cout<<v[i]<<' ';
}
Comentarii
Trimiteți un comentariu