Mergesort madness
What's my goal?
To implement mergesort in 42 different languages.
Why?
Back in June 2006, I enrolled the Numeric Analysis course, in which we had three weeks to do an assignment.
The assignment consisted in analyzing several implementations of Euler's Method. My goal was to implement it in the largest number of languages possible. As time ran out (as it always does), I was forced to abandon the project. Not happy about it, I decided to leave for a crusade against several computer languages, implementing Mergesort in each one of them.
How's it going?
Here's the list of completed implementations.
-
Assembly IA32
View
; ; nasm -felf mergesort.asm -o mergesort.o ; gcc -o mergesort mergesort.o ; BITS 32 global main extern printf section .text main: mov edi, sorted mov esi, array mov ecx, 10 rep movsd push 10 push 0 push sorted call mergesort add esp, 12 push sorted push 10 call print add esp, 8 ret ; 20 max ; 16 med ; 12 min ; 8 array merge: push ebp mov ebp, esp push eax push ecx push edx push edi push esi ;mov edi, temp ;mov eax, 0 ;mov ecx, 10 ;rep stosw mov ecx, [ebp+20] sub ecx, [ebp+12] shl DWORD[ebp+12], 2 shl DWORD[ebp+16], 2 shl DWORD[ebp+20], 2 mov edx, temp ; dest mov edi, [ebp+8] ; middle source add edi, [ebp+16] ; ; messing with the stack. vamos somar aos 3 idxs o addr base mov esi, [ebp+8] add [ebp+12], esi add [ebp+16], esi add [ebp+20], esi mov esi, [ebp+12] .next: ; source != med cmp esi, [ebp+16] jnz .second ; middle != max cmp edi, [ebp+20] jnz .first ; sao os dois iguais. fim jmp .end ; quatro condicoes manhosas... medo. ; vao ser usadas totil de labels .first: cmp esi, [ebp+16] jnz .second ;vamos meter o edi no edx. mov eax, [edi] mov [edx], eax add edx, 4 add edi, 4 jmp .next .second: cmp edi, [ebp+20] jnz .third ;vamos meter o esi no edx mov eax, [esi] mov [edx], eax add edx, 4 add esi, 4 jmp .next .third: mov eax, [esi] cmp eax, [edi] jnl .forth ; meter o esi no edx mov [edx], eax add edx, 4 add esi, 4 jmp .next .forth: mov eax, [edi] mov [edx], eax add edi, 4 add edx, 4 jmp .next .end: ;push temp ;push 10 ;call print ;add esp, 8 mov esi, temp mov edi, [ebp+12] rep movsd ;push DWORD[ebp+8] ;push 10 ;call print ;add esp, 8 ;push endl ;call printf ;add esp, 4 pop esi pop edi pop edx pop ecx pop eax mov esp, ebp pop ebp ret mergesort: push ebp mov ebp, esp push eax mov eax, DWORD[ebp+16] ; max sub eax, [ebp+12] ; min cmp eax, 2 JL .end push edx push ebx xor edx, edx mov ebx, 2 div ebx pop ebx pop edx add eax, [ebp+12] ; med ; siga recursivar. push eax ; max push DWORD[ebp+12] ; min push DWORD[ebp+8] ; array call mergesort add esp, 12 push DWORD[ebp+16] ; max push eax ; min push DWORD[ebp+8] ; array call mergesort add esp, 12 push DWORD[ebp+16] ; max push eax ; med push DWORD[ebp+12] ; min push DWORD[ebp+8] ; array call merge add esp, 16 .end: pop eax mov esp, ebp pop ebp ret print: push ebp ; Prologue mov ebp, esp push ecx push edx mov edx, [ebp+12] mov ecx, [ebp+8] .args: push ecx push edx push DWORD[edx] push format call printf add esp, 8 pop edx pop ecx add edx, 4 LOOP .args push endl call printf add esp, 4 pop edx ; pop ecx ; mov esp, ebp ; pop ebp ; Epilogue ret ; format: db ' %2d', 0 endl: db 10, 0 array: dd 10, 9, 8, 4, 5, 6, 7, 3, 2, 1 section .bss sorted: resd 10 temp: resd 10 -
Bash scripting
View
#!/bin/bash a=(10 9 8 4 5 6 7 3 2 1) # Programar às cegas: Rijo. merge() { local first=2 local second=$(( $1 + 2 )) for i in ${@:2} do if [[ $first -eq $(( $1 + 2 )) ]] then echo ${@:$second:1} ; ((second += 1)) else if [[ $second -eq $(( ${#@} + 1 )) ]] then echo ${@:$first:1} ; ((first += 1)) else if [[ ${@:$first:1} -lt ${@:$second:1} ]] then echo ${@:$first:1} ; ((first += 1)) else echo ${@:$second:1} ; ((second += 1)) fi fi fi done } mergesort() { if [[ $1 -ge 2 ]] then local med=$(( $1 / 2 )) local first=( $(mergesort $med ${@:2:$med}) ) local second=( $(mergesort $(( $1 - $med )) ${@:$(( $med + 2 )):$(( $1 - $med ))}) ) echo $(merge $med ${first[@]} ${second[@]}) else echo $2 fi } echo ${a[@]} ; echo $(mergesort 10 ${a[@]})
-
Brainfuck
View
+>>>>> >>>>> >>>>> >>>>> temporary values stay up here +++++>>>>+++++ +++++ > valores +++++>>>>+++++ ++++ > a +++++>>>>+++++ +++ > ordenar +++++>>>>+++++ > sao +++++>>>>+++++ + > so +++++>>>>+++++ ++ > dez +++++>>>>++++ > valores +++++>>>>+++ > que +++++>>>>++ > acabam +++++>>>>+ > aqui >>> aqui temos um valor indicativo do fim da recursividade > > +++ >>> valor indicativo da necessidade de fazer dois splits > 0 +++++ +++++ > 10 <<<<< voltar ao header tem 5 bytes cada bloco [ while nao for 0 --[++ if nao for 2 (ou seja é 3) copiar o primeiro valor >>>[-<<+< while houver valor pra copiar + marcar o bloco a 4 pra voltarmos [>>>>>] ir para o ultimo bloco >>>+<<< meter la o valor ----[++++<<<<<----]++++ voltar ao bloco marcado - desmarcar o bloco >>>]<<< fim de while repetir o processo pro segundo valor >>>>[-<<+<< + [>>>>>] ir para o ultimo bloco >>>>+<<<< meter la o valor ----[++++<<<<<----]++++ voltar ao bloco marcado - >>>>]<<<< restaurar os valores copiados >[->>+<<]< >>[->>+<<]<< + marcar o bloco como 4 [>>>>>] ir para o ultimo bloco temos os dois valores no ultimo bloco vamos calcular a media agora >>>[-<+>>>+<<]>>[-<<+>>]<<<<< >>>>[->+<<<+>>]>[-<+>]<<<<< neste momento está 0 _ S V W vamos dividir por dois o S >>[ enquanto houver S [>>>+>+<<<<-]>>>>[<<<<+>>>>-]<<<< fazer uma copia do S <<+>>>>> ligar o U -[ se S2 for maior que 1 <<<<<- desligar o U >>--<+< remover 2 do S e aumentar 1 o D >>>>>[-] apagar o S2 ]<<<<< [->>-<<]>> se U apagar S e U ]<< >[->+<]< copiar o D para S agora está 0 _ M V W agora vamos copiar o W pro bloco seguinte >>>>[->>>>>+<<<<<]<<<< copiar o M pro fim do bloco e pro lugar do V no bloco seguinte >>[->>+>>>>+<<<<<<]<< primeiro bloco ++ >>>>[-<<+<+>>>]<<[->>+<<]<< 0 W _ V W >>>[-<+<->>]<[->+<]<< 0 W_V _ V W >-[<+>[-]]< 2/3 0 0 V W >>>>> segundo bloco ++ >>>>[-<<+<+>>>]<<[->>+<<]<< 0 W _ V W >>>[-<+<->>]<[->+<]<< 0 W_V _ V W >-[<+>[-]]< 2/3 0 0 V W ----[++++<<<<<----]++++ encontrar o bloco -- marcar o bloco como 2 --] fim de if ++ >>>>>] fim de while o apontador esta no fim dos blocos que ja estao divididos prontos a serem usados para a ordenacao <<<<< avancar para o ultimo bloco criado acima [ se o bloco nao for nulo que indica que tem que ser aplicado + marcalo com valor 3 copiar os valores para o primeiro bloco indicado pelo valor 1 >>>[-<<< -[+<<<<<-]+ ir para o bloco >>>+<<< ---[+++>>>>>---]+++ >>>]<<< >>>>[-<<<< -[+<<<<<-]+ ir para o bloco >>>>+<<<< ---[+++>>>>>---]+++ >>>>]<<<< acabado de copiar os valores ir para o bloco com eles -[+<<<<<-]+ fazer aqui as cenas e tal tipo calcular a media outra vez e depois fazer as cenas subir pra coiso copiar os valores pra baixo duplicando os pelo caminho >>>[-<<+>>>>+<<] >[-<<+>>>>+<<]<<<< >[->>+>>>>+<<<<<<]< >>[->>+>>>>>+<<<<<<<]<< >>>[-<+>]>[-<<+>>]<<<< >>>>>>[-]<<<<<< divisao por 2 >>[ [->+>+<<]>>[-<<+>>]<< >>+< -[ >- <<-- > >>>>>+<<+ <<< < >[-] ]< >>[-<<[-]>>]<< ]<< ja temos os dados no bloco primeiro 1 _ _ _ _ A B L M H _ _ _ _ _ calcular a soma das diferencas e verificar se é nula >>>>> A [->>>>>+<<<<< <+<<->>>]<[->+<]>> B [->>>>>+<<<<< <<+<->>>]<<[->>+<<]>>>> M [-<<<<+<<+>>>>>>]<<<<[->>>>+<<<<]>>>>> H [-<<<<<+<+>>>>>>]<<<<<[->>>>>+<<<<<] pointer no 5o byte do primeiro bloco > >>>>> [->-<] subtrair o A ao B > pointer no B de baixo ptr(11) [ se A for diferente de B [-]< <<<<< <<< pointer no DA contas manhosas pra calcular o DA&DB a partir do DA e do DB [ [->>+<<] mover o DA >[ ver do DB [->>>>>>>+<<<<<<<] move lo pra longe porque n ha espaco perto <<+>> ]< ] >>[-<<+>>]< restaurar o DA >>>>>>>[-<<<<<<<+>>>>>>>]<<<<<<< << enquanto DA&DB temos que ir ver qual é o menor portanto vamos busca los la abaixo [ o pointer tá no DA&DB buscar o A e ptr(10) >>>> meter o pointer no A [->>>>>+>+<<<<<<]>>>>>[-<<<<<+>>>>>]<<<<< > meter o pointer no B [->>>>+>>+<<<<<<]>>>>[-<<<<+>>>>] +> marcar isto como 1 e meter o pointer no A2 copiar o A2 pra baixo e tal [->>>>> >>>>>+<<<<< <<<<<]>>>>> >>>>> estamos no primeiro numero (5) com A na segunda casa [ enquanto houver numero remover um e copiar pro proximo -[->>>>>+<<<<<]>>>>> ] <+ marcar este cagalhoto como 6 duplicar o numero >>>>[-<<+<+>>>] <<[->>+<<]<< >[-< -[+<<<<<-]+ >>>+<<< ------[++++++>>>>>------]++++++ >]< - desmarcar o cagalhoto -[+<<<<<-]+ procurar o 1 buscar o B e ptr(10) >> pointer no B2 [->>>>> >>>>+<<<<< <<<<]>>>>> >>>> estamos no primeiro numero (5) com B na segunda casa [ enquanto houver numero remover um e copiar pro proximo -[->>>>>+<<<<<]>>>>> ] <++ marcar este cagalhoto como 7 duplicar o numero >>>>[-<<+<+>>>] <<[->>+<<]<< >[-< -[+<<<<<-]+ >>>>+<<<< -------[+++++++>>>>>------- ]+++++++ >]< -- desmarcar o cagalhoto -[+<<<<<-]+ procurar o 1 ja temos o pointer no 1 e os valores v(A) e v(B) tambem ja estao cá ver qual é o maior dos dois; (1) _ _ vA vB less_than(13;14;18); copy(X(13);18;17) >>> [->>>>+>+<<<<<] >>>>[-<<<<+>>>>]<<<< <<< copy(Y(14);19;17) >>>> [->>>+>>+<<<<<] >>>[-<<<+>>>]<<< <<<< meter o pointer no segundo vA(18) >>>>> >>> while (18) [ - dec(18) while (19) >[ <<<+>>> inc(16) - dec(19) [-<<<<+>>>>] move(19;15) ] <<<<[->>>>+<<<<] move(15;19) >>> ] ptr(10) <<< <<<<< copy(X(13);18;17) >>> [->>>>+>+<<<<<] >>>>[-<<<<+>>>>]<<<< <<< copy(Y(14);19;17) >>>> [->>>+>>+<<<<<] >>>[-<<<+>>>]<<< <<<< ptr(16) >>>>> > subtract_to(16;{18;19}) [->>->-<<<] ptr(10) < <<<<< o ptr está no 10 ver qual numero e pra onde levar mudando o A/B e DA/DB e ptr(19) calcular destino ptr(9) copy(9;{11;16};12) <[->>+>+<<<]>>>[-<<<+>>>]<<< ptr(2) subtract_to(2;11;4) <<<< <<< [->>+> >>>>> >-< <<<<< <<<]>>[-<<+>>]<< ptr(3) subtract_to(3;11;4) > [->+> >>>>> >-< <<<<< <<]>[-<+>]< fazer punhes ptr(2) dec(2) <- ptr(5) inc(5) >>> + ptr(18) >>>>> >>>>> >>> while(18) OU SEJA o B é menor que A [ ptr(6) inc(6) <<< <<<<< <<<< + ptr(5) dec(5) < - ptr(3) dec(3) << - ptr(2) inc(2) < + ptr(13) >>> >>>>> >>> swap(13;14;12) [-<+>]>[-<+>]<<[->>+<<]> ptr(18) >> >>> clear(18) [-] ] ptr(19) > clear(19) [-] ptr(11) <<<< <<<< levar o 13 pro mark(5) indicado pelo 11 e voltar pro mark(1) aka ptr(10) move(11;21) [- >>>>> >>>>>+<<<<< <<<<<] ptr(13) move(13;{22}) >> [->> >>>>> >>+<< <<<<< <<] ptr(14) clear(14) >[-] ptr(20) > >>>>> >[ dec(mark(5):1) move(mark(5):1;mark(5):6) -[->>>>>+<<<<<] ptr(mark(5):2) move(mark(5):2;mark(5):7) >[->>>>>+<<<<<] ptr(mark(5):6) >>>> ]< estamos num mark(5) e é preciso mover o :2 pro :3 >>[->+<]<< voltar pro mark(1) -[+<<<<<-]+ - desmarca lo ptr(1) aka DA&DB <<<<< <<<< recalcular DA&DB com ptr(1) o pointer aqui tem que estar no DA&DB and(2;3;1;{4;10}) [-] >[ ptr(4) clear(4) ptr(2) >>[-]<< move(2;4) [->>+<<] >[ [->>>>>>>+<<<<<<<] move(3;10) <<+>> ptr(1) inc(1) ptr(3) ]< ptr(4) ] >>[-<<+>>]< move(4;2) >>>>>>>[-<<<<<<<+>>>>>>>]<<<<<<< move(10;3) << ptr(1) ] pointer no DA&DB ptr(1) ptr(2) > [ copiar os da primeira metade pro final destination marcar 10 ptr(10) inc(10) ptr(5) >>> >>>>> + <<<<< copy(5;21;11) ptr(11) [->>>>> >+>>>> >>>>> >+< <<<<< <<<<< <<<<<]+>>>>> >[-< <<<<<+>>>>> >] ptr(21) >>>>> >>>>> [-[->>>>>+<<<<<]>>>>>]< >>>>[-<<+<+>>>]<<<< >>[->>+<<]<< -[+ >[-<<<<<+>>>>>]< <<<<<-]+ >[->+<]< estamos em ptr(10) copy(9;11;13) < [->>+>>+<<<<] >>>>[-<<<<+>>>>]<<< subtract_to(2;11;4) <<<<< <<< [->>+> >>>>> >-< <<<<< <<<]>>[-<<+>>]< subtract_to(3;11;4) [->+> >>>>> >-< <<<<< <<]>[-<+>]> >>>>> >[->>>>> >>>>>+<<<<< <<<<<]< >>[->>>>> >>>>>+<<<<< <<<<<]<< >>>>> >>>>> >[ -[->>>>>+<<<<<] >[->>>>>+<<<<<]< >>>>> ]< >>[->+<]<< -[+<<<<<-]+ desmarcar - ptr(2) dec(2) <<<<< <<< - ] ptr(3) > [ copiar os da primeira metade pro final destination marcar 10 ptr(10) inc(10) ptr(6) >> >>>>> + <<<< copy(6;21;11) ptr(11) [->>>> >+>>>> >>>>> >+< <<<<< <<<<< <<<<]+>>>> >[-< <<<<+>>>> >] ptr(21) >>>>> >>>>> [-[->>>>>+<<<<<]>>>>>]< >>>>[-<<+<+>>>]<<<< >>[->>+<<]<< -[+ >[-<<<<<+>>>>>]< <<<<<-]+ >[->+<]< estamos em ptr(10) copy(9;11;13) < [->>+>>+<<<<] >>>>[-<<<<+>>>>]<<< subtract_to(2;11;4) <<<<< <<< [->>+> >>>>> >-< <<<<< <<<]>>[-<<+>>]< subtract_to(3;11;4) [->+> >>>>> >-< <<<<< <<]>[-<+>]> >>>>> estamos em 10 >[->>>>> >>>>>+<<<<< <<<<<]< >>[->>>>> >>>>>+<<<<< <<<<<]<< >>>>> >>>>> >[ -[->>>>>+<<<<<] >[->>>>>+<<<<<]< >>>>> ]< >>[->+<]<< -[+<<<<<-]+ estamos em 10 outra vez desmarcar - ptr(3) dec(3) <<<<< << - ] assentar os valores do array temporario move(7;21) move(9;22) >> >>[->>> >>>>> >>>>> >+< <<<<< <<<<< <<<] >>[-> >>>>> >>>>> >>+<< <<<<< <<<<< <] aproveitar e marcar o 10 > + >>>>> >>>>> >[-[->>>>>+<<<<<] >-[->>>>>+<<<<<]< >>>>>]< >>[-[->>>>>+<<<<<]>>[-]<< >[->+<]< >>>>>]<< -[+<<<<<-]+ - voltar a meter o pointer no B de baixo ptr(11) > [-] ] voltar a meter o pointer no inicio do bloco 1 < <<<<< <<<<< pointer no inicio do bloco 1 limpar as cenas no bloco 1 >[-]>[-]>[-]>[-]> [-]>[-]>[-]>[-]>[-]> [-]>[-]>[-]>[-]>[-]> [-]>[-]>[-]>[-]>[-] <<<< <<<<< <<<<< <<<<< ---[+++>>>>>---]+++ ir para o bloco marcado --- eliminar o bloco <<<<< avançar para o proximo bloco ] imprimir as vaquinhas como letras de B a K -[+<<<<<-]+ -----[+++++>>>>>-----]+++++ [ >>>> +++++ +++++ +++++ +++++ +++++ +++++ +++++ +++++ +++++ +++++ +++++ +++++ +++++ . ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- ----- < +++++ +++++ +++++ +++++ +++++ +++++ ++ . ----- ----- ----- ----- ----- ----- -- >> ] +++++ +++++.----- -----
-
C
View
#include <stdio.h> int lst[] = {10, 9, 8, 4, 5, 6, 7, 3, 2, 1}; void merge(int * lst, int a, int b, int s) { int tmp[10], ti = a, ai = a, bi = b; while (ai < b || bi < s) { if (bi == s) tmp[ti++] = lst[ai++]; else if (ai == b) tmp[ti++] = lst[bi++]; else if (lst[ai] < lst[bi]) tmp[ti++] = lst[ai++]; else tmp[ti++] = lst[bi++]; } for (ti = a; ti < s; ti++) lst[ti] = tmp[ti]; } void mergesort(int * lst, int a, int b) { if (b-a < 2) return; mergesort(lst, a, a + (b-a)/2); mergesort(lst, a + (b-a)/2, b); merge(lst, a, a + (b-a)/2, b); } int main() { int i; mergesort(lst, 0, 10); for (i = 0; i < 10; i++) printf("%d ", lst[i]); printf("\n"); return 0; }
-
C++
View
#include <iostream> #include <vector> #include <algorithm> using namespace std; template<typename IT> void merge(IT begin, IT middle, IT end, IT res) { IT a = begin, b = middle, r = res; while (a < middle && b < end) if (*a < *b) *r++ = *a++; else *r++ = *b++; while (a < middle) *r++ = *a++; while (b < end) *r++ = *b++; while (begin < end) *begin++ = *res++; } template<typename IT> void mergesort(IT begin, IT end, IT res) { int s = end-begin; if (s > 1) { IT middle = begin+s/2; mergesort(begin, middle, res); mergesort(middle, end, res); merge(begin, middle, end, res); } } int main() { int lst[] = {10, 9, 8, 4, 5, 6, 7, 3, 2, 1}; int sorted[10]; mergesort(lst, lst + 10, sorted); for (int i = 0; i < 10; i++) cout << sorted[i] << " "; cout << endl; return 0; } -
C++ Template MetaProgramming
View
#include <iostream> using namespace std; /* If, then, else. */ template<bool v, typename A, typename B> struct mif {}; template<typename A, typename B> struct mif<true, A, B> { typedef A value; }; template<typename A, typename B> struct mif<false, A, B> { typedef B value; }; /* List definition */ template<int v, typename T> struct cons { static const int value = v; typedef T rest; }; struct nil { }; /* List size definition */ template<typename T> struct len { enum { value = 1 + len<typename T::rest>::value }; }; template<> struct len<nil> { enum { value = 0 }; }; /* First N elements */ template<typename T, int n> struct head { typedef cons< T::value, typename head<typename T::rest, n - 1>::value > value; }; template<int n> struct head<nil, n> { typedef nil value; }; template<typename T> struct head<T, 0> { typedef nil value; }; /* Remove first N elements */ template<typename T, int n> struct tail { typedef typename tail<typename T::rest, n - 1>::value value; }; template<int n> struct tail<nil, n> { typedef nil value; }; template<typename T> struct tail<T, 0> { typedef T value; }; /* Merge two sorted lists */ template<typename A, typename B> struct merge { typedef typename mif< (A::value < B::value), cons<A::value, typename merge<typename A::rest, B>::value >, cons<B::value, typename merge<A, typename B::rest>::value > >::value value; }; template<typename A> struct merge<A, nil> { typedef A value; }; template<typename B> struct merge<nil, B> { typedef B value; }; /* Sort a list */ template<typename A, bool v = (len<A>::value < 2)> struct mergesort { typedef A value; }; template<typename A> struct mergesort<A, false> { typedef typename merge< typename mergesort<typename head<A, (len<A>::value / 2)>::value>::value, typename mergesort<typename tail<A, (len<A>::value / 2)>::value>::value >::value value; }; /* Print a list */ template<typename A> void print() { cout << A::value << endl; print<typename A::rest>(); } template<> void print<nil>() { } int main() { /* Create a list */ typedef cons<10, cons<9, cons<8, cons<7, cons<4, cons<5, cons<6, cons<3, cons<2, cons<1, nil> > > > > > > > > > x; /* Sort it */ typedef mergesort<x>::value sorted; /* Print it */ print<sorted>(); return 0; } -
Common Lisp
View
(defun list-head (lst n) (if (eq n 0) '() (cons (car lst) (list-head (cdr lst) (- n 1))))) (defun list-tail (lst n) (if (eq n 0) lst (list-tail (cdr lst) (- n 1)))) (defun _merge (lst-a lst-b) (cond ((not lst-a) lst-b) ((not lst-b) lst-a) ((< (car lst-a) (car lst-b)) (cons (car lst-a) (_merge (cdr lst-a) lst-b))) (T (cons (car lst-b) (_merge lst-a (cdr lst-b)))))) (defun mergesort (lst) (if (eq (length lst) 1) lst (_merge (mergesort (list-head lst (truncate (length lst) 2))) (mergesort (list-tail lst (truncate (length lst) 2))))))
-
Erlang
View
-module(mergesort). -export([mergesort/1]). merge(A, []) -> A; merge([], B) -> B; merge([Ha|Ta], [Hb|Tb]) -> if Ha < Hb -> [Ha | merge(Ta, [Hb|Tb])]; true -> [Hb | merge([Ha|Ta], Tb)] end. mergesort([]) -> []; mergesort([E]) -> [E]; mergesort(L) -> {A, B} = lists:split(trunc(length(L)/2), L), merge(mergesort(A), mergesort(B)).
-
Fortran 95
View
program testmergesort integer lst(10) lst = (/ 10, 9, 8, 4, 5, 6, 7, 3, 2, 1 /) call mergesort(lst, 0, 10) call show(lst) end program testmergesort subroutine _merge(lst, a, middle, b) integer a integer b integer middle integer lst(10) integer tmp(10) integer ai integer bi integer ti integer x ai = a bi = middle ti = a do while ((ai .lt. middle) .or. (bi .lt. b)) if (ai .eq. middle) then tmp(ti+1) = lst(bi+1) bi = bi + 1 else if (bi .eq. b) then tmp(ti+1) = lst(ai+1) ai = ai + 1 else if (lst(ai+1) .lt. lst(bi+1)) then tmp(ti+1) = lst(ai+1) ai = ai + 1 else tmp(ti+1) = lst(bi+1) bi = bi + 1 end if ti = ti + 1 end do do x = a, b - 1 lst(x + 1) = tmp(x + 1) end do end recursive subroutine mergesort(lst, a, b) integer a integer b integer lst(10) integer diff diff = b - a if (diff .lt. 2) then return else diff = diff / 2 call mergesort(lst, a, a + diff) call mergesort(lst, a + diff, b) call _merge(lst, a, a + diff, b) endif end subroutine show(lst) integer lst(10) integer x do x = 1, 10 print 100, lst(x) end do 100 format (i0) end
-
Haskell
View
list_tail :: [Integer] -> Integer -> [Integer] list_tail lst 0 = lst list_tail (e:lst) n = list_tail lst (n - 1) list_head :: [Integer] -> Integer -> [Integer] list_head lst 0 = [] list_head (e:lst) n = e:(list_head lst (n - 1)) merge :: [Integer] -> [Integer] -> [Integer] merge a [] = a merge [] b = b merge (ea:a) (eb:b) = if ea < eb then ea:(merge a (eb:b)) else eb:(merge (ea:a) b) mergesort :: [Integer] -> [Integer] mergesort lst = let ln = toInteger (length lst) in if ln == 1 then lst else merge (mergesort (list_head lst (div ln 2))) (mergesort (list_tail lst (div ln 2))) main = let lst = [10, 9, 8, 4, 5, 6, 7, 3, 2, 1] in do print (merge_sort lst) -
J
View
mergesort =. ( $:@ ((<.@-:@#)({.)([)) merge $:@ ((<.@-:@(-@#))({.)([)) )^:(1<#) min =. (<./@({.!._@[,{.!._@])) merge =. (min , (((min=({.!._@[)) }. [)) $: (((min=({.!._@])) }. ])) )^:(0&<@(#@([,])))
-
Java
View
import java.util.*; class mergesort { public static void merge(int[] lst, int a, int m, int b) { int[] tmp = new int[10]; int ai = a, bi = m, ti = a; while (ai < m || bi < b) { if (ai == m) tmp[ti++] = lst[bi++]; else if (bi == b) tmp[ti++] = lst[ai++]; else if (lst[ai] < lst[bi]) tmp[ti++] = lst[ai++]; else tmp[ti++] = lst[bi++]; } for (ti = a; ti < b; ti++) lst[ti] = tmp[ti]; } public static void mergesort(int[] lst, int a, int b) { if (b-a < 2) return; mergesort(lst, a, a + (b-a) / 2); mergesort(lst, a + (b-a) / 2, b); merge(lst, a, a + (b-a) / 2, b); } public static void main(String[] args) { int[] lst = new int[] {10, 9, 8, 4, 5, 6, 7, 3, 2, 1}; mergesort(lst, 0, 10); for (int i = 0; i < 10; i++) System.out.print(lst[i] + " "); System.out.println("\n"); } }
-
Javascript
View
function merge(lst, a, m, b) { tmp = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]; ai = a; bi = m; ti = a; while (ai < m || bi < b) { if (ai == m) tmp[ti++] = lst[bi++]; else if (bi == b) tmp[ti++] = lst[ai++]; else if (lst[ai] < lst[bi]) tmp[ti++] = lst[ai++]; else tmp[ti++] = lst[bi++]; } for (i = a; i < b; i++) lst[i] = tmp[i]; } function mergesort(lst, a, b) { if (b - a < 2) return; m = ((b - a) / 2)|0; mergesort(lst, a, a + m); mergesort(lst, a + m, b); merge(lst, a, a + m, b); } lst = [10, 9, 8, 4, 5, 6, 7, 3, 2, 1]; mergesort(lst, 0, 10); print(lst); -
LOLCODE 1.0
View
HAI CAN HAS STDIO? I HAS A NUMBERS LOL 0 IN MAH NUMBERS R 10 LOL 1 IN MAH NUMBERS R 9 LOL 2 IN MAH NUMBERS R 8 LOL 3 IN MAH NUMBERS R 5 LOL 4 IN MAH NUMBERS R 6 LOL 5 IN MAH NUMBERS R 7 LOL 6 IN MAH NUMBERS R 4 LOL 7 IN MAH NUMBERS R 3 LOL 8 IN MAH NUMBERS R 2 LOL 9 IN MAH NUMBERS R 1 I HAS A Q I HAS A QSIZE LOL QSIZE R 0 I HAS A ITERATION LOL 0 IN MAH ITERATION R 0 LOL 1 IN MAH ITERATION R 10 LOL 0 IN MAH Q R ITERATION UPZ QSIZE!! I HAS A COUTNER LOL COUTNER R 0 IM IN YR MERGESORT IZ COUTNER SMALR THAN QSIZE? NOWAI GTFO KTHX LOL ITERATION R COUTNER IN MAH Q I HAS A MIDDLE LOL MIDDLE R 1 IN MAH ITERATION NERF 0 IN MAH ITERATION IZ MIDDLE SMALR THAN 2? NOWAI OVARZ MIDDLE!!2 UPZ MIDDLE!!0 IN MAH ITERATION I HAS A NEWITERATR LOL 0 IN MAH NEWITERATR R 0 IN MAH ITERATION LOL 1 IN MAH NEWITERATR R MIDDLE LOL QSIZE IN MAH Q R NEWITERATR UPZ QSIZE!! I HAS A SECONDITERATR LOL 0 IN MAH SECONDITERATR R MIDDLE LOL 1 IN MAH SECONDITERATR R 1 IN MAH ITERATION LOL QSIZE IN MAH Q R SECONDITERATR UPZ QSIZE!! KTHX UPZ COUTNER!! KTHX LOL COUTNER R QSIZE IM IN YR QUEUEA IZ COUTNER LIEK 0? GTFO KTHX NERFZ COUTNER!! LOL ITERATION R COUTNER IN MAH Q IZ 1 IN MAH ITERATION NERF 0 IN MAH ITERATION SMALR THAN 2? NOWAI I HAS A NUMBERSCOPY LOL NCID R 0 LOL LOW R 0 IN MAH ITERATION LOL HIGH R 1 IN MAH ITERATION LOL MED R HIGH NERF LOW OVARZ MED!!2 UPZ MED!!LOW LOL LVAL R LOW LOL HVAL R MED IM IN YR MERGE IZ NCID LIEK HIGH NERF LOW? GTFO KTHX IZ LVAL NOT LIEK MED AND HVAL NOT LIEK HIGH? YARLY IZ LVAL IN MAH NUMBERS SMALR THAN HVAL IN MAH NUMBERS? YARLY LOL NCID IN MAH NUMBERSCOPY R LVAL IN MAH NUMBERS UPZ LVAL!! NOWAI LOL NCID IN MAH NUMBERSCOPY R HVAL IN MAH NUMBERS UPZ HVAL!! KTHX NOWAI IZ LVAL NOT LIEK MED? YARLY LOL NCID IN MAH NUMBERSCOPY R LVAL IN MAH NUMBERS UPZ LVAL!! NOWAI LOL NCID IN MAH NUMBERSCOPY R HVAL IN MAH NUMBERS UPZ HVAL!! KTHX KTHX UPZ NCID!! KTHX IM IN YR COPY IZ NCID LIEK 0? GTFO KTHX NERFZ NCID!! LOL SUM R NCID UP LOW LOL SUM IN MAH NUMBERS R NCID IN MAH NUMBERSCOPY KTHX KTHX KTHX VISIBLE NUMBERS KTHXBYE -
Maxima
View
mergesort(list) := block([len: length(list), h: entier(length(list)/2)], if len > 1 then merge(mergesort(rest(list, h-len)), mergesort(rest(list, h))) else list); merge(a, b) := if length(a) * length(b) = 0 then append(a, b) else if first(a) < first(b) then cons(first(a), merge(rest(a), b)) else cons(first(b), merge(a, rest(b)));
-
mIRC Scripting
View
alias recurse { return $eval($+($,$1),2) } alias merge { if !$1 || !$2 { return $1 $2 } var %ta, %tb, %ha = $gettok($1,1,32), %hb = $gettok($2,1,32) if (%ha < %hb) { %ta = $gettok($1,2-,32) | %tb = $2 } else { %ta = $1 | %tb = $gettok($2,2-,32) } return $iif(%ha < %hb, %ha, %hb) $recurse(merge( %ta , %tb )) } alias mergesort { if ($numtok($1,32) < 2) return $1 var %m = $floor($calc($numtok($1,32) / 2)) var %a = $gettok($1,$+(1,-,%m),32) var %b = $gettok($1,$+($calc(%m + 1),-),32) return $merge( $recurse(mergesort( %a )), $recurse(mergesort( %b )) ) } echo -a $mergesort(10 9 8 4 5 6 7 3 2 1) -
Perl
View
use strict; use warnings; sub merge { my($s, @b) = @_; my(@a) = splice(@b, $s); if (@a * @b == 0) { return @a, @b; } my($head) = $a[0] < $b[0] ? shift(@a) : shift(@b); return $head, merge(int(@a), @a, @b); } sub mergesort { my($half) = int(@_ / 2); if ($half == 0) { return @_; } return merge($half, mergesort(splice(@_, $half)), mergesort(@_)); } my(@sorted) = mergesort(10, 9, 8, 4, 5, 6, 7, 3, 2, 1); print(join(" ", @sorted) . "\n");
-
PHP
View
<? function merge(&$lst, $start, $middle, $end) { $tmp = array(); $i = $start; $j = $middle; while ($i < $middle && $j < $end) $tmp[] = $lst[($lst[$i] < $lst[$j] ? $i++ : $j++)]; $tmp = array_merge($tmp, array_slice($lst, $i, $middle-$i), array_slice($lst, $j, $end-$j)); for ($i = $start; $i < $end; $i++) $lst[$i] = $tmp[$i - $start]; } function mergesort(&$lst, $a, $b) { if ($b - $a < 2) return; $half = floor(($b + $a) / 2); mergesort($lst, $a, $half); mergesort($lst, $half, $b); merge($lst, $a, $half, $b); } $lst = array(10, 9, 8, 4, 5, 6, 7, 3, 2, 1); mergesort($lst, 0, 10); print_r($lst); ?> -
Portugol
View
início variável inteiro pilha[100000] variável inteiro valores[10] <- {9, 7, 10, 4, 2, 3, 1, 8, 6, 5} variável inteiro temporário[10] variável inteiro i <- 0 variável inteiro tamanho_da_pilha <- 1 pilha[0] <- 0 pilha[1] <- 10 enquanto i < tamanho_da_pilha faz se pilha[i*2+1] - pilha[i*2] > 1 então variavel inteiro média <- (pilha[i*2] + pilha[i*2+1]) / 2 se média - pilha[i*2] > 1 então pilha[tamanho_da_pilha*2] <- pilha[i*2] pilha[tamanho_da_pilha*2+1] <- média tamanho_da_pilha <- tamanho_da_pilha + 1 fimSe se pilha[i*2+1] - média > 1 então pilha[tamanho_da_pilha*2] <- média pilha[tamanho_da_pilha*2+1] <- pilha[i*2+1] tamanho_da_pilha <- tamanho_da_pilha + 1 fimSe fimSe i <- i + 1 fimEnquanto para i de tamanho_da_pilha-1 até 0 passo -1 variável inteiro média <- (pilha[i*2] + pilha[i*2+1])/2 variável inteiro c <- pilha[i*2] variável inteiro j <- pilha[i*2] variável inteiro k <- média enquanto j < média e k < pilha[i*2+1] faz se valores[j] < valores[k] então temporário[c] <- valores[j] j <- j + 1 senão temporário[c] <- valores[k] k <- k + 1 fimSe c <- c + 1 fimEnquanto enquanto j < média faz temporário[c] <- valores[j] c <- c + 1 j <- j + 1 fimEnquanto enquanto k < pilha[i*2+1] faz temporário[c] <- valores[k] c <- c + 1 k <- k + 1 fimEnquanto para j de pilha[i*2] até pilha[i*2+1]-1 valores[j] <- temporário[j] próximo próximo para i de 0 até 9 escrever valores[i], "\n" próximo fim
-
Prolog
View
list_head(_, 0, []). list_head([H|T], N, [H|Sub]) :- N1 is N-1, list_head(T, N1, Sub). list_tail(T, 0, T). list_tail([_|T], N, R) :- N1 is N-1, list_tail(T, N1, R). merge(A, [], A). merge([], B, B). merge([Ha|Ta], [Hb|Tb], [Ha|Sub]) :- Ha < Hb, merge(Ta, [Hb|Tb], Sub). merge([Ha|Ta], [Hb|Tb], [Hb|Sub]) :- Ha >= Hb, merge([Ha|Ta], Tb, Sub). mergesort([H], [H]). mergesort(List, Sorted) :- length(List, Number), Half is Number // 2, list_head(List, Half, H), list_tail(List, Half, T), mergesort(H, A), mergesort(T, B), merge(A, B, Sorted). test(Sorted) :- mergesort([10, 9, 8, 4, 5, 6, 7, 3, 2, 1], Sorted). -
Python
View
def merge(a, b): if len(a)*len(b) == 0: return a+b v = (a[0] < b[0] and a or b).pop(0) return [v] + merge(a, b) def mergesort(lst): if len(lst) < 2: return lst m = len(lst)/2 return merge(mergesort(lst[:m]), mergesort(lst[m:])) mlst = [10, 9, 8, 4, 5, 6, 7, 3, 2, 1] sorted = mergesort(mlst) print sorted -
Ruby
View
def merge(a, b) r = [] r << (a.first < b.first ? a : b).shift while a.length*b.length > 0 return r+a+b end def mergesort(lst) return lst if lst.size == 1 a = mergesort(lst[0, lst.size/2]) b = mergesort(lst[lst.size/2, lst.size]) return merge(a, b) end mlst = [10, 9, 8, 5, 6, 7, 4, 3, 2, 1] sorted = mergesort(mlst) puts sorted -
Scheme
View
(define list-head (lambda (lst n) (if (eq? n 0) '() (cons (car lst) (list-head (cdr lst) (- n 1)))))) (define list-tail (lambda (lst n) (if (eq? n 0) lst (list-tail (cdr lst) (- n 1))))) (define merge (lambda (lst-a lst-b) (cond ((null? lst-a) lst-b) ((null? lst-b) lst-a) (else (if (< (car lst-a) (car lst-b)) (cons (car lst-a) (merge (cdr lst-a) lst-b)) (cons (car lst-b) (merge lst-a (cdr lst-b))) ))))) (define mergesort (lambda (lst) (if (eq? (length lst) 1) lst (merge (mergesort (list-head lst (quotient (length lst) 2))) (mergesort (list-tail lst (quotient (length lst) 2))) )))) (mergesort '(10 9 8 4 5 6 7 3 2 1))
-
VDM++
View
class Mergesort operations public Merge(a : seq of int, b : seq of int) r : seq of int == return if len(a)*len(b) = 0 then a ^ b else if a(1) < b(1) then [a(1)] ^ Merge(tl(a), b) else Merge(b, a); public Sort(lst : seq of int) r : seq of int == return if len(lst) < 2 then lst else Merge(Sort(lst(1, ..., len(lst) div 2)), Sort(lst(len(lst) div 2 + 1, ..., len(lst)))); end Mergesort -
XSL
View
<?xml version="1.0" encoding="UTF-8"?> <xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform" xmlns:exsl="http://exslt.org/common" extension-element-prefixes="exsl" version="1.0"> <xsl:template match="/"> <html> <head> <title>Mergesort madness</title> </head> <body> <h1>Previous</h1> <xsl:apply-templates /> <h1>Sorted</h1> <xsl:variable name='sorted'> <xsl:call-template name='mergesort'> <xsl:with-param name='lst'> <xsl:copy-of select='list' /> </xsl:with-param> </xsl:call-template> </xsl:variable> <xsl:apply-templates select='exsl:node-set($sorted)/list' /> </body> </html> </xsl:template> <xsl:template name='merge'> <xsl:param name='a' /> <xsl:param name='b' /> <xsl:choose> <xsl:when test='count(exsl:node-set($a)/list/element)=0'> <xsl:copy-of select='exsl:node-set($b)/list' /> </xsl:when> <xsl:when test='count(exsl:node-set($b)/list/element)=0'> <xsl:copy-of select='exsl:node-set($a)/list' /> </xsl:when> <xsl:when test='exsl:node-set($a)/list/*[1]/@value < exsl:node-set($b)/list/*[1]/@value'> <xsl:variable name='r'> <xsl:call-template name='merge'> <xsl:with-param name='a'> <list><xsl:copy-of select='exsl:node-set($a)/list/*[count(preceding-sibling::*) > 0]' /> </list> </xsl:with-param> <xsl:with-param name='b' select='exsl:node-set($b)' /> </xsl:call-template> </xsl:variable> <list> <xsl:copy-of select='exsl:node-set($a)/list/element[1]' /> <xsl:copy-of select='exsl:node-set($r)/list/element' /> </list> </xsl:when> <xsl:otherwise> <xsl:variable name='r'> <xsl:call-template name='merge'> <xsl:with-param name='a' select='exsl:node-set($a)' /> <xsl:with-param name='b'> <list><xsl:copy-of select='exsl:node-set($b)/list/*[count(preceding-sibling::*) > 0]' /> </list> </xsl:with-param> </xsl:call-template> </xsl:variable> <list> <xsl:copy-of select='exsl:node-set($b)/list/element[1]' /> <xsl:copy-of select='exsl:node-set($r)/list/element' /> </list> </xsl:otherwise> </xsl:choose> </xsl:template> <xsl:template name='mergesort'> <xsl:param name='lst' /> <xsl:variable name='size' select='count(exsl:node-set($lst)/list/element)' /> <xsl:choose> <xsl:when test='$size < 2'> <xsl:copy-of select='exsl:node-set($lst)' /> </xsl:when> <xsl:otherwise> <xsl:call-template name='merge'> <xsl:with-param name='a'> <xsl:call-template name='mergesort'> <xsl:with-param name='lst'> <list><xsl:copy-of select='exsl:node-set($lst)/list/*[count(following-sibling::*) >= $size div 2]' /> </list> </xsl:with-param> </xsl:call-template> </xsl:with-param> <xsl:with-param name='b'> <xsl:call-template name='mergesort'> <xsl:with-param name='lst'> <list><xsl:copy-of select='exsl:node-set($lst)/list/*[count(following-sibling::*) < $size div 2]' /> </list> </xsl:with-param> </xsl:call-template> </xsl:with-param> </xsl:call-template> </xsl:otherwise> </xsl:choose> </xsl:template> <xsl:template match='list'> <ol><xsl:apply-templates /></ol> </xsl:template> <xsl:template match='element'> <li><xsl:value-of select='@value' /></li> </xsl:template> </xsl:stylesheet>