Asembler x86 Poniższy kod jest prostą iteracyjną implementacją algorytmu sortowania przez scalanie. Sortowane są w kolejności rosnącej elementy tablicy znaków zgodnie z ich kodem ASCII.

section .data ; ciąg znaków do posortowania msg1 db '9876543210ZYXQVUTSRQPONMLKJIHGFEDCBAzyxwvutsrqponmlkjihgfedcba543210' ; tablica pustych znaków msg2 db ' ' src dd 0 ; wskaźnik do aktualnej źródłowej tablicy dst dd 0 ; wskaźnik do aktualnej tablicy wynikowej cnt dd 68 ; rozmiar tablicy wpisany na stałe, znajdujący się także ; wpisany na stałe w linii 115 tego kodu źródłowego

bufor dd 0 ; ofset kolejnego znaku tablicy dst skok dd 2 ; skok do początku następnej pary podciągów ofset dd 0 ; indeks dd 0 ;

esiend dd 0 ; graniczne indeksy scalanych podciągów ediend dd 0 ; srcend dd 0 ;

endl db 0x0a ; znak końca linii

section .text global _start

_start: mov [src],dword msg1 ; początkowy wskaźnik do tablicy źródłowej mov [dst],dword msg2 ; i docelowej

petla2: mov [bufor],dword 0 ; reset wartości indeksowych na początku mov [ofset],dword 0 ; każdego obiegu pętli głównej mov [indeks],dword 0

mov edx,[src] ; ustawienie granicznych indeksów podciągu drugiego add edx,[cnt] ; na koniec tablicy źródłowej dec edx ; mov [srcend],edx ;

petla1: mov ecx,[skok] ; ecx zawiera liczbę znaków w obu podciągach do ; wstawienia do ciągu wynikowego

shr ecx,1 ; tymczasowa modyfikacja ecx na potrzeby poniższych ; instrukcji

mov esi,[src] ; esi ustawione na początek podciągu pierwszego add esi,[ofset]

mov edi,esi ; add edi,ecx ; edi ustawione na początek podciągu drugiego

mov al,[esi] ; rejestry eax oraz ebx zawierają kolejne elementy mov bl,[edi] ; porównywane w celu scalenia podciągów

dec ecx ; tymczasowa modyfikacja ecx na potrzeby poniższych ; instrukcji

mov edx,esi ; ustawienie granicznych indeksów podciągu pierwszego add edx,ecx ; na koniec podciągu pierwszego mov [esiend],edx ;

mov edx,edi ; ustawienie granicznych indeksów podciągu drugiego add edx,ecx ; na koniec podciągu drugiego zwiększając wartość o CF mov [ediend],edx ;

inc ecx ; przywrócenie pierwotnej wartości ECX, który shl ecx,1 ; będzie wykorzystywany w petli 'loop porownaj'

mov edx,[dst] ; wyznaczenie pierwszego indeksu ciągu wynikowego add edx,[ofset] ; mov [bufor],edx ; kolejny indeks przechowywany jest w zmiennej bufor

add [ofset],ecx ; zwiększenie ofsetu o wartość skoku na potrzeby kolejnego ; obiegu pętli porownaj: mov edx,[bufor]

cmp esi,[srcend] ; jeżeli pierwszy podciąg doszedł do końca tablicy źródłowej jg koniec ; rozpoczyna sie nowy obieg petli

cmp edi,[srcend] ; jeżeli drugi podciąg doszedł do końca tablicy źródłowej jg pierwszy ; do tablicy wynikowej wpisywane są pozostałe ; elementy z pierwszego podciągu

cmp esi,[esiend] ; jeżeli doszliśmy do końca pierwszego podciągu jg drugi ; do tablicy wynikowej wpisywane są pozostałe ; elementy z drugiego podciągu

cmp edi,[ediend] ; jeżeli doszliśmy do końca drugiego podciągu jg pierwszy ; do tablicy wynikowej wpisywane są pozostałe ; elementy z pierwszego podciągu

cmp al,bl ; porównuje kolejne elementy ze scalanych podciągów jl pierwszy ; kopiuje mniejszy z nich do tablicy wynikowej

drugi: mov [edx],bl ; jeżeli BL<=AL, wstawiamy BL do ciągu wynikowego inc edi ; przechodzimy do następnego znaku podciągu drugiego mov bl,[edi] ; i ładujemy do rejestru BL jmp koniec

pierwszy: mov [edx],al ; jeżeli AL<BL, wstawiamy AL do ciągu wynikowego inc esi ; przechodzimy do następnego znaku podciągu pierwszego mov al,[esi] ; i ładujemy go do rejestru AL

koniec: inc edx mov [bufor],edx inc dword [indeks]; loop porownaj ; skok do kolejnego porównania

cmp [indeks], dword 68 ; dopóki nie przeszliśmy końcowego elementu ciągu jl petla1 ; wynikowego, to porównujemy elementy kolejnych par podciągów

; wyświetla pośrednie tablice wynikowe mov eax, 4 ; eax=4, write() syscall mov ebx, 1 ; ebx=1, stdout mov ecx, [dst] ; adres tekstu do ecx mov edx, [cnt] ; długość tekstu do edx int 0x80 ; wywołanie funkcji systemowej

; wyświetla znak końca linii mov eax, 4 ; eax=4, write() syscall mov ebx, 1 ; ebx=1, stdout mov ecx, endl ; adres tekstu do ecx mov edx, 1 ; długość tekstu do edx int 0x80 ; wywołanie funkcji systemowej

mov eax,[src] ; w celu oszczędności pamięci mov ebx,[dst] ; tablica wynikowa staje się teraz źródłową, mov [src],ebx ; a aktualna źródłowa będzie nadpisana zawartością mov [dst],eax ; nowej tablicy wynikowej

mov ecx,[skok] ; mnożymy skok przez 2, jeżeli nowy skok shl ecx,1 ; jest mniejszy od dwukrotności rozmiaru mov [skok],ecx ; tablicy, wykonujemy skok do początku pętli głównej shr ecx,1 ; cmp ecx,[cnt] ; rozpoczynając scalanie od pierwszego znaku jl petla2 ;

; kończy program mov eax, 1 ; exit() syscall mov ebx, 5 ; kod wyjścia int 0x80 ;

Pascal Struktura tablica jest tablicą, której elementy mogą być zmieniane, argumenty start, koniec są całkowitoliczbowe.

procedure merge(tablica, start, środek, koniec);

var tab_pom : array [0..koniec-start] of integer; i,j,k : integer;

begin

i := start; k := 0; j := środek + 1;

while (i <= środek) and (j <= koniec) begin if tablica[i] <= tablica[j] then begin tab_pom[k] := tab[i] i := i + 1; end else begin tab_pom[k] := tab[j]; j := j + 1; end; k := k + 1; end;

while (i <= środek) begin tab_pom[k] := tab[i]; i := i + 1; k := k + 1; end;

while (j koniec then begin środek := (start + koniec) div 2; merge_sort(tablica, start, środek); merge_sort(tablica, środek + 1, koniec); merge (tablica, start, środek, koniec); end;

end;

JavaScript Porównanie mergsorterów znalezionych na: http://edu.i-lo.tarnow.pl/inf/alg/003_sort/0013.php oraz http://www.algorytm.org/algorytmy-sortowania/sortowanie-przez-scalanie-mergesort/merge-d.html Wszystko gotowe do odpalenia w konsoli firebuga

function merge(pocz, sr, kon) { var i,j,q; t = new Array(); for (i=pocz; i<=kon; i++) t[i]=tab[i]; // Skopiowanie danych do tablicy pomocniczej i=pocz; j=sr+1; q=pocz; // Ustawienie wskaźników tablic while (i<=sr && j<=kon) { // Przenoszenie danych z sortowaniem ze zbiorów pomocniczych do tablicy głównej tab_iter++;

if (t[i]<t[j]) tab[q++]=t[i++]; else tab[q++]=t[j++];

while (i<=sr) tab[q++]=t[i++]; // Przeniesienie nie skopiowanych danych ze zbioru pierwszego w przypadku, gdy drugi zbiór się skończył }

function mergesort(pocz, kon) { var sr; if (pocz<kon) { sr=Math.floor((pocz+kon)/2); mergesort(pocz, sr); // Dzielenie lewej części mergesort(sr+1, kon); // Dzielenie prawej części merge(pocz, sr, kon); // Łączenie części lewej i prawej

function onemerge(i_p, i_k) { var i_s,i1,i2,i; p = new Array(); i_s = Math.floor((i_p + i_k + 1) / 2); if(i_s - i_p > 1) onemerge(i_p, i_s - 1); if(i_k - i_s > 0) onemerge(i_s, i_k); i1 = i_p; i2 = i_s; for(i = i_p; i d[i2]))) ? d[i2++] : d[i1++];

for(i = i_p; i <= i_k; i++) d[i] = p[i]; }

tab_iter = d_iter = 0; source= new Array(); for(counter = 0; counter < 100; counter++) source[counter] = Math.floor(Math.random() * 100); tab = d = source;

mergesort(0, source.length-1); onemerge(0,source.length-1);

console.log(tab); console.log('tab iter'+tab_iter); console.log('##################'); console.log(d); console.log('d iter'+d_iter);

Python def scal(n): if len(n)==1:return n s=int(len(n)/2) a=scal(n[:s]) b=scal(n[s:]) a=a[::-1] b=b[::-1] i=a.pop() e=b.pop() c=[] for x in range(len(n)): if(i<e): c.append(i) if not len(a)==0: i=a.pop() else: c.append(e) for q in b: c.append(q) break else: c.append(e) if not len(b)==0: e=b.pop() else: c.append(i) for q in a: c.append(q) break

return c Licencja