Sorting algorithms/Merge sort: Difference between revisions
m
→{{header|Standard ML}}: minor reformat of SML and extra example
m (→{{header|Standard ML}}: minor reformat of SML and extra example) |
|||
| (87 intermediate revisions by 17 users not shown) | |||
Line 68:
{{trans|Python}}
<
[Int] result
V left_idx = 0
Line 99:
V arr = [7, 6, 5, 9, 8, 4, 3, 1, 2, 0]
print(merge_sort(arr))</
{{out}}
Line 109:
{{trans|BBC BASIC}}
The program uses ASM structured macros and two ASSIST macros (XDECO, XPRNT) to keep the code as short as possible.
<
MAIN CSECT
STM R14,R12,12(R13) save caller's registers
Line 272:
RPGI EQU 3 pgi
RBS EQU 0 bs
END MAIN</
{{out}}
<pre>
Line 280:
=={{header|AArch64 Assembly}}==
{{works with|as|Raspberry Pi 3B version Buster 64 bits}}
<syntaxhighlight lang="aarch64 assembly">
/* ARM assembly AARCH64 Raspberry PI 3B */
/* program mergeSort64.s */
Line 495:
/* for this file see task include a file in language AArch64 assembly */
.include "../includeARM64.inc"
</syntaxhighlight>
=={{header|ACL2}}==
<
(if (endp (rest xys))
(mv xys nil)
Line 531:
(split xs)
(mrg (msort ys)
(msort zs)))))</
=={{header|Action!}}==
Action! language does not support recursion. Therefore an iterative approach has been proposed.
<
PROC PrintArray(INT ARRAY a INT size)
Line 639:
Test(c,8)
Test(d,12)
RETURN</
{{out}}
[https://gitlab.com/amarok8bit/action-rosetta-code/-/raw/master/images/Merge_sort.png Screenshot from Atari 8-bit computer]
Line 665:
=={{header|ActionScript}}==
<
{
//Arrays of length 1 and 0 are always sorted
Line 714:
result[m++] = right[k];
return result;
}</
=={{header|Ada}}==
This example creates a generic package for sorting arrays of any type. Ada allows array indices to be any discrete type, including enumerated types which are non-numeric. Furthermore, numeric array indices can start at any value, positive, negative, or zero. The following code handles all the possible variations in index types.
<
type Element_Type is private;
type Index_Type is (<>);
Line 726:
package Mergesort is
function Sort(Item : Collection_Type) return Collection_Type;
end MergeSort;</
<
-----------
Line 789:
end Sort;
end Mergesort;</
The following code provides an usage example for the generic package defined above.
<
with Mergesort;
Line 809:
Print(List);
Print(List_Sort.Sort(List));
end Mergesort_Test;</
{{out}}
<pre>
Line 821:
a different memory location is expensive, then the optimised version should
be used as the DATA elements are handled indirectly.
<
PROC merge sort = ([]DATA m)[]DATA: (
Line 861:
[32]CHAR char array data := "big fjords vex quick waltz nymph";
print((merge sort(char array data), new line));</
{{out}}
<pre>
Line 869:
# avoids FLEX array copies and manipulations
# avoids type DATA memory copies, useful in cases where DATA is a large STRUCT
<
IF LWB m >= UPB m THEN
m
Line 906:
[]REF CHAR result = opt merge sort(data);
FOR i TO UPB result DO print((result[i])) OD; print(new line)</
{{out}}
<pre>
Line 914:
=={{header|AppleScript}}==
<
In-place, iterative binary merge sort
Merge sort algorithm: John von Neumann, 1945.
Line 1,029:
set aList to {22, 15, 98, 82, 22, 4, 58, 70, 80, 38, 49, 48, 46, 54, 93, 8, 54, 2, 72, 84, 86, 76, 53, 37, 90}
sort(aList, 1, -1) -- Sort items 1 thru -1 of aList.
return aList</
{{output}}
<
=={{header|ARM Assembly}}==
{{works with|as|Raspberry Pi}}
<syntaxhighlight lang="arm assembly">
/* ARM assembly Raspberry PI */
/* program mergeSort.s */
Line 1,233:
/***************************************************/
.include "../affichage.inc"
</syntaxhighlight>
=={{header|Arturo}}==
<syntaxhighlight lang="arturo">merge: function [a,b,left,middle,right][
leftLen: middle - left
rightLen: right - middle
l: 0
r: leftLen
loop left..dec middle 'i [
b\[l]: a\[i]
l: l + 1
]
loop middle..dec right 'i [
b\[r]: a\[i]
r: r + 1
]
l: 0
r: leftLen
i: left
while [and? l < leftLen r < leftLen + rightLen][
if? b\[l] < b\[r] [
a\[i]: b\[l]
l: l + 1
]
else [
a\[i]: b\[r]
r: r + 1
]
i: i + 1
]
while [l < leftLen][
a\[i]: b\[l]
l: l + 1
i: i + 1
]
while [r < leftLen + rightLen][
a\[i]: b\[r]
r: r + 1
i: i + 1
]
]
mergeLR: function [a,b,left,right][
if 1 >= right - left -> return ø
mid: (left + right) / 2
mergeLR a b left mid
mergeLR a b mid right
merge a b left mid right
]
mergeSort: function [arr][
result: new arr
b: new array.of:size result 0
mergeLR result b 0 size result
return result
]
print mergeSort [3 1 2 8 5 7 9 4 6]</syntaxhighlight>
{{out}}
<pre>1 2 3 4 5 6 7 8 9</pre>
=={{header|Astro}}==
<
if m.lenght <= 1: return m
let middle = floor m.lenght / 2
Line 1,251 ⟶ 1,318:
let arr = [7, 6, 5, 9, 8, 4, 3, 1, 2, 0]
print mergesort arr</
=={{Header|ATS}}==
Line 1,258 ⟶ 1,325:
This algorithm modifies the links in the list, rather than allocate new cons-pairs. It requires no garbage collector.
<
(* Mergesort in ATS2, for linear lists. *)
(*------------------------------------------------------------------*)
Line 1,358 ⟶ 1,425:
list_vt_merge$lt<a> (x, y) =
list_vt_mergesort$lt<a> (x, y)
(* You can make SMALL larger than 1 and write small_sort as a fast
Line 1,427 ⟶ 1,492:
end
(*------------------------------------------------------------------*)</
{{out}}
Line 1,433 ⟶ 1,498:
before : 22, 15, 98, 82, 22, 4, 58, 70, 80, 38, 49, 48, 46, 54, 93, 8, 54, 2, 72, 84, 86, 76, 53, 37, 90
after : 2, 4, 8, 15, 22, 22, 37, 38, 46, 48, 49, 53, 54, 54, 58, 70, 72, 76, 80, 82, 84, 86, 90, 93, 98</pre>
Footnote: Rather than directly write a mergesort for "ordinary" non-linear lists, I would write a routine to do the following:
* make a copy of the list;
* cast the copy to a linear list;
* sort the linear list;
* cast the result to non-linear list, and return the casted result.
This way, new cons-pairs are allocated only once.
The same thing can be done in other languages, of course. An interesting thing about this ATS implementation, though, is it proves the result is of the same length as the input. It does not, however, prove that the result satisfies the order predicate.
===A mergesort for non-linear lists of integers, guaranteeing a sorted result===
The following program not only sorts a list of integers, but verifies that the result is sorted. It is the simplest implementation I could think of that does that. It works by having a special kind of list that can be consed only in sorted order.
The length of the result also is verified. However, there is no proof that the result contains the same data as the input.
<syntaxhighlight lang="ats">//--------------------------------------------------------------------
//
// A mergesort for 32-bit signed integers.
//
//--------------------------------------------------------------------
#include "share/atspre_staload.hats"
(*------------------------------------------------------------------*)
#define ENTIER_MAX 2147483647
(* We do not include the most negative two's-complement number. *)
stadef entier (i : int) = ~ENTIER_MAX <= i && i <= ENTIER_MAX
sortdef entier = {i : int | entier i}
typedef entier (i : int) = [entier i] int i
typedef entier = [i : entier] entier i
datatype sorted_entier_list (int, int) =
| sorted_entier_list_nil (0, ENTIER_MAX)
| {n : nat}
{i, j : entier | ~(j < i)}
sorted_entier_list_cons (n + 1, i) of
(entier i, sorted_entier_list (n, j))
typedef sorted_entier_list (n : int) =
[i : entier] sorted_entier_list (n, i)
typedef sorted_entier_list =
[n : int] sorted_entier_list n
infixr ( :: ) :::
#define NIL list_nil ()
#define :: list_cons
#define SNIL sorted_entier_list_nil ()
#define ::: sorted_entier_list_cons
(*------------------------------------------------------------------*)
extern prfn
lemma_sorted_entier_list_param
{n : int}
(lst : sorted_entier_list n)
:<prf> [0 <= n] void
extern fn
sorted_entier_list_length
{n : int}
(lst : sorted_entier_list n)
:<> [0 <= n] int n
extern fn
sorted_entier_list_merge
{m, n : int}
{i, j : entier}
(lst1 : sorted_entier_list (m, i),
lst2 : sorted_entier_list (n, j))
:<> sorted_entier_list (m + n, min (i, j))
extern fn
entier_list_mergesort
{n : int}
(lst : list (entier, n)) (* An ordinary list. *)
:<!wrt> sorted_entier_list n
extern fn
sorted_entier_list2list
{n : int}
(lst : sorted_entier_list n)
:<> list (entier, n)
overload length with sorted_entier_list_length
overload merge with sorted_entier_list_merge
overload mergesort with entier_list_mergesort
overload to_list with sorted_entier_list2list
(*------------------------------------------------------------------*)
primplement
lemma_sorted_entier_list_param {n} lst =
case+ lst of
| SNIL => ()
| _ ::: _ => ()
implement
sorted_entier_list_length {n} lst =
(* This implementation is tail-recursive. *)
let
fun
count {m : nat | m <= n} .<n - m>.
(lst : sorted_entier_list (n - m),
m : int m)
:<> [0 <= n] int n =
case+ lst of
| SNIL => m
| _ ::: tail => count {m + 1} (tail, succ m)
prval () = lemma_sorted_entier_list_param lst
in
count (lst, 0)
end
implement
sorted_entier_list_merge (lst1, lst2) =
(* This implementation is *NOT* tail recursive. It will use O(m+n)
stack space. *)
let
fun
recurs {m, n : nat}
{i, j : entier} .<m + n>.
(lst1 : sorted_entier_list (m, i),
lst2 : sorted_entier_list (n, j))
:<> sorted_entier_list (m + n, min (i, j)) =
case+ lst1 of
| SNIL => lst2
| i ::: tail1 =>
begin
case+ lst2 of
| SNIL => lst1
| j ::: tail2 =>
if ~(j < i) then
i ::: recurs (tail1, lst2)
else
j ::: recurs (lst1, tail2)
end
prval () = lemma_sorted_entier_list_param lst1
prval () = lemma_sorted_entier_list_param lst2
in
recurs (lst1, lst2)
end
implement
entier_list_mergesort lst =
let
fun
recurs {m : nat} .<m>.
(lst : list (entier, m),
m : int m)
:<!wrt> sorted_entier_list m =
if m = 1 then
let
val+ head :: NIL = lst
in
head ::: SNIL
end
else if m = 0 then
SNIL
else
let
val m_left = m \g1int_ndiv 2
val m_right = m - m_left
val @(left, right) = list_split_at (lst, m_left)
val left = recurs (list_vt2t left, m_left)
and right = recurs (right, m_right)
in
left \merge right
end
prval () = lemma_list_param lst
in
recurs (lst, length lst)
end
implement
sorted_entier_list2list lst =
(* This implementation is *NOT* tail recursive. It will use O(n)
stack space. *)
let
fun
recurs {n : nat} .<n>.
(lst : sorted_entier_list n)
:<> list (entier, n) =
case+ lst of
| SNIL => NIL
| head ::: tail => head :: recurs tail
prval () = lemma_sorted_entier_list_param lst
in
recurs lst
end
(*------------------------------------------------------------------*)
fn
print_Int_list
{n : int}
(lst : list (Int, n))
: void =
let
fun
loop {n : nat} .<n>.
(lst : list (Int, n))
: void =
case+ lst of
| NIL => ()
| head :: tail =>
begin
print! (" ");
print! (head);
loop tail
end
prval () = lemma_list_param lst
in
loop lst
end
implement
main0 () =
let
val example_list =
$list (22, 15, 98, 82, 22, 4, 58, 70, 80, 38, 49, 48, 46, 54,
93, 8, 54, 2, 72, 84, 86, 76, 53, 37, 90)
val sorted_list = mergesort example_list
in
print! ("unsorted ");
print_Int_list example_list;
println! ();
print! ("sorted ");
print_Int_list (to_list sorted_list);
println! ()
end
(*------------------------------------------------------------------*)</syntaxhighlight>
{{out}}
<pre>patscc -O3 -DATS_MEMALLOC_GCBDW mergesort_task_verified.dats -lgc && ./a.out
unsorted 22 15 98 82 22 4 58 70 80 38 49 48 46 54 93 8 54 2 72 84 86 76 53 37 90
sorted 2 4 8 15 22 22 37 38 46 48 49 53 54 54 58 70 72 76 80 82 84 86 90 93 98</pre>
''Postscript''. One might try adding a line such as
<pre>val x = 3 ::: 2 ::: SNIL</pre>
to the program and see that the compiler will report it as erroneous, on grounds that "2 is not less than 3" is unsatisfied.
== [[AutoHotkey_L]] ==
Line 1,438 ⟶ 1,757:
This version of Merge Sort only needs '''n''' locations to sort.
[http://www.autohotkey.com/forum/viewtopic.php?t=77693&highlight=| AHK forum post]
<
Test := []
Line 1,500 ⟶ 1,819:
Return Array
}</
=={{header|AutoHotkey}}==
Contributed by Laszlo on the ahk [http://www.autohotkey.com/forum/post-276483.html#276483 forum]
<
MsgBox % MSort("xxx")
MsgBox % MSort("3,2,1")
Line 1,540 ⟶ 1,859:
}
}
}</
=={{header|
==={{header|BBC BASIC}}===
<syntaxhighlight lang="bbcbasic">DEFPROC_MergeSort(Start%,End%)
REM *****************************************************************
REM This procedure Merge Sorts the chunk of data% bounded by
Line 1,598 ⟶ 1,918:
ENDWHILE
ENDPROC</
Usage would look something like this example which sorts a series of 1000 random integers:
<
Size%=1000
Line 1,614 ⟶ 1,934:
PROC_MergeSort(1,Size%)
END</
==={{header|Chipmunk Basic}}===
{{works with|Chipmunk Basic|3.6.4}}
{{trans|Quite BASIC}}
<syntaxhighlight lang="qbasic">100 REM Sorting algorithms/Merge sort
110 CLS
120 LET N = 10
130 LET C = 0
140 OPTION BASE 1
150 DIM A(10)
160 DIM B(10)
170 RANDOMIZE TIMER
180 GOSUB 810
190 REM Print the random array
200 PRINT "unsort ";
210 GOSUB 860
220 REM Sort the array
230 GOSUB 300
240 PRINT " sort ";
250 REM Print the sorted array
260 GOSUB 860
270 PRINT "Number of iterations: ";C
290 END
300 REM Merge sort the list A of length N
310 REM Using the array B for temporary storage
320 REM
330 REM === Split phase ===
340 REM C counts the number of split/merge iterations
350 LET C = C+1
360 LET X = 1
370 LET Y = 1
380 LET Z = N
390 GOTO 410
400 IF A(X) < A(X-1) THEN GOTO 470
410 LET B(Y) = A(X)
420 LET Y = Y+1
430 LET X = X+1
440 IF Z < Y THEN GOTO 500
450 GOTO 400
460 IF A(X) < A(X-1) THEN GOTO 410
470 LET B(Z) = A(X)
480 LET Z = Z-1
490 LET X = X+1
500 IF Z < Y THEN GOTO 530
510 GOTO 460
520 REM
530 REM === Merge Phase ===
540 REM Q means "we're done" (or "quit")
550 REM Q is 1 until we know that this is _not_ the last iteration
560 LET Q = 1
570 LET X = 1
580 LET Y = 1
590 LET Z = N
600 REM First select the smaller item
610 IF B(Y) < B(Z) THEN GOTO 710 ELSE GOTO 750
620 REM Check if the loop is done
630 IF Z < Y THEN GOTO 790
640 REM If both items are smaller then start over with the smallest
650 IF B(Y) >= A(X-1) OR B(Z) >= A(X-1) THEN GOTO 680
660 LET Q = 0
670 GOTO 600
680 REM Pick the smallest item that represents an increase
690 IF B(Z) < B(Y) AND B(Z) >= A(X-1) THEN GOTO 750
700 IF B(Z) > B(Y) AND B(Y) < A(X-1) THEN GOTO 750
710 LET A(X) = B(Y)
720 LET Y = Y+1
730 LET X = X+1
740 GOTO 620
750 LET A(X) = B(Z)
760 LET Z = Z-1
770 LET X = X+1
780 GOTO 620
790 IF Q = 0 THEN GOTO 330
800 RETURN
810 REM Create a random list of N integers
820 FOR I = 1 TO N
830 LET A(I) = FLOOR(RND(100))
840 NEXT I
850 RETURN
860 REM PRINT the list A
870 FOR I = 1 TO N
880 PRINT A(I);" ";
890 NEXT I
900 PRINT
910 RETURN</syntaxhighlight>
==={{header|Minimal BASIC}}===
{{trans|Quite BASIC}}
<syntaxhighlight lang="qbasic">120 LET N = 10
130 LET C = 0
140 OPTION BASE 1
150 DIM A(10)
160 DIM B(10)
170 RANDOMIZE
180 GOSUB 810
190 REM Print the random array
200 PRINT "unsort ";
210 GOSUB 860
220 REM Sort the array
230 GOSUB 300
240 PRINT " sort ";
250 REM Print the sorted array
260 GOSUB 860
270 PRINT "Number of iterations: "; C
290 GOTO 950
300 REM Merge sort the list A of length N
310 REM Using the array B for temporary storage
320 REM
330 REM === Split phase ===
340 REM C counts the number of split/merge iterations
350 LET C = C+1
360 LET X = 1
370 LET Y = 1
380 LET Z = N
390 GOTO 410
400 IF A(X) < A(X-1) THEN 470
410 LET B(Y) = A(X)
420 LET Y = Y+1
430 LET X = X+1
440 IF Z < Y THEN 500
450 GOTO 400
460 IF A(X) < A(X-1) THEN 410
470 LET B(Z) = A(X)
480 LET Z = Z-1
490 LET X = X+1
500 IF Z < Y THEN 530
510 GOTO 460
520 REM
530 REM === Merge Phase ===
540 REM Q means "we're done" (or "quit")
550 REM Q is 1 until we know that this is _not_ the last iteration
560 LET Q = 1
570 LET X = 1
580 LET Y = 1
590 LET Z = N
600 REM First select the smaller item
610 IF B(Y) < B(Z) THEN 710
615 IF B(Y) > B(Z) THEN 750
620 REM Check if the loop is done
630 IF Z < Y THEN 790
640 REM If both items are smaller then start over with the smallest
650 IF B(Y) >= A(X-1) THEN 680
655 IF B(Z) >= A(X-1) THEN 680
660 LET Q = 0
670 GOTO 600
680 REM Pick the smallest item that represents an increase
690 IF B(Z) < B(Y) THEN 695
692 IF B(Z) > B(Y) THEN 700
695 IF B(Z) >= A(X-1) THEN 750
700 IF B(Z) > B(Y) THEN 705
705 IF B(Y) < A(X-1) THEN 750
710 LET A(X) = B(Y)
720 LET Y = Y+1
730 LET X = X+1
740 GOTO 620
750 LET A(X) = B(Z)
760 LET Z = Z-1
770 LET X = X+1
780 GOTO 620
790 IF Q = 0 THEN 330
800 RETURN
810 REM Create a random list of N integers
820 FOR I = 1 TO N
830 LET A(I) = INT((RND * 100) + .5)
840 NEXT I
850 RETURN
860 REM PRINT the list A
870 FOR I = 1 TO N
880 PRINT A(I); " ";
890 NEXT I
900 PRINT
910 RETURN
950 END</syntaxhighlight>
==={{header|Quite BASIC}}===
<syntaxhighlight lang="qbasic">100 REM Sorting algorithms/Merge sort
110 CLS
120 LET N = 10
130 LET C = 0
150 ARRAY A
160 ARRAY B
180 GOSUB 810
190 REM Print the random array
200 PRINT "unsort ";
210 GOSUB 860
220 REM Sort the array
230 GOSUB 300
240 PRINT " sort ";
250 REM Print the sorted array
260 GOSUB 860
270 PRINT "Number of iterations: "; C
290 END
300 REM Merge sort the list A of length N
310 REM Using the array B for temporary storage
320 REM
330 REM === Split phase ===
340 REM C counts the number of split/merge iterations
350 LET C = C+1
360 LET X = 1
370 LET Y = 1
380 LET Z = N
390 GOTO 410
400 IF A(X) < A(X-1) THEN GOTO 470
410 LET B(Y) = A(X)
420 LET Y = Y+1
430 LET X = X+1
440 IF Z < Y THEN GOTO 500
450 GOTO 400
460 IF A(X) < A(X-1) THEN GOTO 410
470 LET B(Z) = A(X)
480 LET Z = Z-1
490 LET X = X+1
500 IF Z < Y THEN GOTO 530
510 GOTO 460
520 REM
530 REM === Merge Phase ===
540 REM Q means "we're done" (or "quit")
550 REM Q is 1 until we know that this is _not_ the last iteration
560 LET Q = 1
570 LET X = 1
580 LET Y = 1
590 LET Z = N
600 REM First select the smaller item
610 IF B(Y) < B(Z) THEN GOTO 710 ELSE GOTO 750
620 REM Check if the loop is done
630 IF Z < Y THEN GOTO 790
640 REM If both items are smaller then start over with the smallest
650 IF B(Y) >= A(X-1) OR B(Z) >= A(X-1) THEN GOTO 680
660 LET Q = 0
670 GOTO 600
680 REM Pick the smallest item that represents an increase
690 IF B(Z) < B(Y) AND B(Z) >= A(X-1) THEN GOTO 750
700 IF B(Z) > B(Y) AND B(Y) < A(X-1) THEN GOTO 750
710 LET A(X) = B(Y)
720 LET Y = Y+1
730 LET X = X+1
740 GOTO 620
750 LET A(X) = B(Z)
760 LET Z = Z-1
770 LET X = X+1
780 GOTO 620
790 IF Q = 0 THEN GOTO 330
800 RETURN
810 REM Create a random list of N integers
820 FOR I = 1 TO N
830 LET A(I) = FLOOR(RND(100))
840 NEXT I
850 RETURN
860 REM PRINT the list A
870 FOR I = 1 TO N
880 PRINT A(I); " ";
890 NEXT I
900 PRINT
910 RETURN</syntaxhighlight>
=={{header|BCPL}}==
<
let mergesort(A, n) be if n >= 2
Line 1,654 ⟶ 2,228:
mergesort(array, length)
write("After: ", array, length)
$)</
{{out}}
<pre>Before: 4 65 2 -31 0 99 2 83 782 1
Line 1,660 ⟶ 2,234:
=={{header|C}}==
<
#include <stdlib.h>
Line 1,697 ⟶ 2,271:
printf("%d%s", a[i], i == n - 1 ? "\n" : " ");
return 0;
}</
{{out}}
<pre>
Line 1,703 ⟶ 2,277:
-31 0 1 2 2 4 65 83 99 782
</pre>
Non-recursive variant:
<syntaxhighlight lang="c">#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* x and y are sorted, copy nx+ny sorted values to r */
void merge(int nx, int*x, int ny, int*y, int*r) {
int i= 0, j= 0, k= 0;
while (i<nx && j<ny) {
int a= x[i], b= y[j];
if (a<b) {
r[k++]= a;
i++;
} else {
r[k++]= b;
j++;
}
}
if (i<nx) {
memcpy(r+k, i+x, (nx-i)*sizeof (int));
} else if (j<ny) {
memcpy(r+k, j+y, (ny-j)*sizeof (int));
}
}
void mergesort(int ny, int *y) {
int stride= 1, mid, *r= y, *t, *x= malloc(ny*sizeof (int));
while (stride < ny) {
stride= 2*(mid= stride);
for (int i= 0; i<ny; i+= stride) {
int lim= mid;
if (i+stride >= ny) {
if (i+mid >= ny) {
memcpy(i+x, i+y, (ny-i)*sizeof (int));
continue;
}
lim= ny-(i+mid);
}
merge(mid, i+y, lim, i+mid+y, i+x);
}
t= x; x= y; y=t;
}
if (y!=r) {
memcpy(r, y, ny*sizeof(int));
x= y;
}
free(x);
}
int main () {
int a[] = {4, 65, 2, -31, 0, 99, 2, 83, 782, 1};
int n = sizeof a / sizeof a[0];
int i;
for (i = 0; i < n; i++)
printf("%d%s", a[i], i == n - 1 ? "\n" : " ");
mergesort(n, a);
for (i = 0; i < n; i++)
printf("%d%s", a[i], i == n - 1 ? "\n" : " ");
return 0;
}</syntaxhighlight>
{{out}}
<pre>
4 65 2 -31 0 99 2 83 782 1
-31 0 1 2 2 4 65 83 99 782</pre>
=={{header|C sharp|C#}}==
{{works with|C sharp|C#|3.0+}}
<
using System;
Line 1,830 ⟶ 2,470:
}
#endregion
}</
'''Example''':
<
using System;
Line 1,842 ⟶ 2,482:
Console.WriteLine(String.Join(" ", entries));
}
}</
{{out}}
<pre>1 2 2 3 4 5 6 6 7</pre>
=={{header|C++}}==
<
#include <algorithm> // for std::inplace_merge
#include <functional> // for std::less
Line 1,867 ⟶ 2,507:
{
mergesort(first, last, std::less<typename std::iterator_traits<RandomAccessIterator>::value_type>());
}</
=={{header|Clojure}}==
{{trans|Haskell}}
<
(defn merge [left right]
(cond (nil? left) right
Line 1,885 ⟶ 2,525:
(let [[left right] (split-at (/ (count list) 2) list)]
(merge (merge-sort left) (merge-sort right)))))
</syntaxhighlight>
=={{header|COBOL}}==
Cobol cannot do recursion, so this version simulates recursion. The working storage is therefore pretty complex, so I have shown the whole program, not just the working procedure division parts.
<
PROGRAM-ID. MERGESORT.
AUTHOR. DAVE STRATFORD.
Line 2,181 ⟶ 2,821:
HC-999.
EXIT.</
=={{header|CoffeeScript}}==
<
# A more sophisticated version would do more in-place optimizations.
merge_sort = (arr) ->
Line 2,208 ⟶ 2,848:
do ->
console.log merge_sort [2,4,6,8,1,3,5,7,9,10,11,0,13,12]</
{{out}}
<pre>
Line 2,216 ⟶ 2,856:
=={{header|Common Lisp}}==
<
(let ((split (floor (length sequence) 2)))
(if (zerop split)
Line 2,222 ⟶ 2,862:
(merge result-type (merge-sort result-type (subseq sequence 0 split) predicate)
(merge-sort result-type (subseq sequence split) predicate)
predicate))))</
<tt>merge</tt> is a standard Common Lisp function.
Line 2,228 ⟶ 2,868:
> (merge-sort 'list (list 1 3 5 7 9 8 6 4 2) #'<)
(1 2 3 4 5 6 7 8 9)
=={{header|Component Pascal}}==
{{works with|BlackBox Component Builder}}
Inspired by the approach used by the Modula-2[https://rosettacode.org/wiki/Sorting_algorithms/Merge_sort#Recursive_on_linked_list] application.
This an implementation of the stable merge sort algorithm for linked lists.
The merge sort algorithm is often the best choice for sorting a linked list.
The `Sort` procedure reduces the number of traversals by calculating the length only once at the beginning of the sorting process.
This optimization leads to a more efficient sorting process, making it faster, especially for large input lists.
Two modules are provided - for implementing and for using the merge sort .
<syntaxhighlight lang="oberon2">
MODULE RosettaMergeSort;
TYPE Template* = ABSTRACT RECORD END;
(* Abstract Procedures: *)
(* Return TRUE if list item`front` comes before list item `rear` in the sorted order, FALSE otherwise *)
(* For the sort to be stable `front` comes before `rear` if they are equal *)
PROCEDURE (IN t: Template) Before- (front, rear: ANYPTR): BOOLEAN, NEW, ABSTRACT;
(* Return the next item in the list after `s` *)
PROCEDURE (IN t: Template) Next- (s: ANYPTR): ANYPTR, NEW, ABSTRACT;
(* Update the next pointer of list item `s` to the value of list `next` - Return the modified `s` *)
PROCEDURE (IN t: Template) Set- (s, next: ANYPTR): ANYPTR, NEW, ABSTRACT;
(* Merge sorted lists `front` and `rear` - Return the merged sorted list *)
PROCEDURE (IN t: Template) Merge (front, rear: ANYPTR): ANYPTR, NEW;
BEGIN
IF front = NIL THEN RETURN rear END;
IF rear = NIL THEN RETURN front END;
IF t.Before(front, rear) THEN
RETURN t.Set(front, t.Merge(t.Next(front), rear))
ELSE
RETURN t.Set(rear, t.Merge(front, t.Next(rear)))
END
END Merge;
(* Sort the first `n` items in the list `s` and drop them from `s` *)
(* Return the sorted `n` items *)
PROCEDURE (IN t: Template) TakeSort (n: INTEGER; VAR s: ANYPTR): ANYPTR, NEW;
VAR k: INTEGER; front, rear: ANYPTR;
BEGIN
IF n = 1 THEN (* base case: if `n` is 1, return the head of `s` *)
front := s; s := t.Next(s); RETURN t.Set(front, NIL)
END;
(* Divide the first `n` items of `s` into two sorted parts *)
k := n DIV 2;
front := t.TakeSort(k, s);
rear := t.TakeSort(n - k, s);
RETURN t.Merge(front, rear) (* Return the merged parts *)
END TakeSort;
(* Perform a merge sort on `s` - Return the sorted list *)
PROCEDURE (IN t: Template) Sort* (s: ANYPTR): ANYPTR, NEW;
VAR n: INTEGER; r: ANYPTR;
BEGIN
IF s = NIL THEN RETURN s END; (* If `s` is empty, return `s` *)
(* Count of items in `s` *)
n := 0; r := s; (* Initialize the item to be counted to `s` *)
WHILE r # NIL DO INC(n); r := t.Next(r) END;
RETURN t.TakeSort(n, s) (* Return the sorted list *)
END Sort;
END RosettaMergeSort.
</syntaxhighlight>
Interface extracted from implementation:
<syntaxhighlight lang="oberon2">
DEFINITION RosettaMergeSort;
TYPE
Template = ABSTRACT RECORD
(IN t: Template) Before- (front, rear: ANYPTR): BOOLEAN, NEW, ABSTRACT;
(IN t: Template) Next- (s: ANYPTR): ANYPTR, NEW, ABSTRACT;
(IN t: Template) Set- (s, next: ANYPTR): ANYPTR, NEW, ABSTRACT;
(IN t: Template) Sort (s: ANYPTR): ANYPTR, NEW
END;
END RosettaMergeSort.
</syntaxhighlight>
Use the merge sort implementation from `RosettaMergeSort` to sort a linked list of characters:
<syntaxhighlight lang="oberon2">
MODULE RosettaMergeSortUse;
(* Import Modules: *)
IMPORT Sort := RosettaMergeSort, Out;
(* Type Definitions: *)
TYPE
(* a character list *)
List = POINTER TO RECORD
value: CHAR;
next: List
END;
(* Implement the abstract record type Sort.Template *)
Order = ABSTRACT RECORD (Sort.Template) END;
Asc = RECORD (Order) END;
Bad = RECORD (Order) END;
Desc = RECORD (Order) END;
(* Abstract Procedure Implementations: *)
(* Return the next node in the linked list *)
PROCEDURE (IN t: Order) Next (s: ANYPTR): ANYPTR;
BEGIN RETURN s(List).next END Next;
(* Set the next pointer of list item `s` to `next` - Return the updated `s` *)
PROCEDURE (IN t: Order) Set (s, next: ANYPTR): ANYPTR;
BEGIN
IF next = NIL THEN s(List).next := NIL
ELSE s(List).next := next(List) END;
RETURN s
END Set;
(* Ignoring case, compare characters to determine ascending order in the sorted list *)
(* For the sort to be stable `front` comes before `rear` if they are equal *)
PROCEDURE (IN t: Asc) Before (front, rear: ANYPTR): BOOLEAN;
BEGIN
RETURN CAP(front(List).value) <= CAP(rear(List).value)
END Before;
(* Unstable sort!!! *)
PROCEDURE (IN t: Bad) Before (front, rear: ANYPTR): BOOLEAN;
BEGIN
RETURN CAP(front(List).value) < CAP(rear(List).value)
END Before;
(* Ignoring case, compare characters to determine descending order in the sorted list *)
(* For the sort to be stable `front` comes before `rear` if they are equal *)
PROCEDURE (IN t: Desc) Before (front, rear: ANYPTR): BOOLEAN;
BEGIN
RETURN CAP(front(List).value) >= CAP(rear(List).value)
END Before;
(* Helper Procedures: *)
(* Takes a string and converts it into a linked list of characters *)
PROCEDURE Explode (str: ARRAY OF CHAR): List;
VAR i: INTEGER; h, t: List;
BEGIN
i := LEN(str$);
WHILE i # 0 DO
t := h; NEW(h);
DEC(i); h.value := str[i];
h.next := t
END;
RETURN h
END Explode;
(* Outputs the characters in a linked list as a string in quotes *)
PROCEDURE Show (s: List);
VAR i: INTEGER;
BEGIN
Out.Char('"');
WHILE s # NIL DO Out.Char(s.value); s := s.next END;
Out.Char('"')
END Show;
(* Main Procedure: *)
PROCEDURE Use*;
VAR a: Asc; b: Bad; d: Desc; s: List;
BEGIN
s := Explode("A quick brown fox jumps over the lazy dog");
Out.String("Before:"); Out.Ln; Show(s); Out.Ln;
s := a.Sort(s)(List); (* Ascending stable sort *)
Out.String("After Asc:"); Out.Ln; Show(s); Out.Ln;
s := b.Sort(s)(List); (* Ascending unstable sort *)
Out.String("After Bad:"); Out.Ln; Show(s); Out.Ln;
s := d.Sort(s)(List); (* Descending stable sort *)
Out.String("After Desc:"); Out.Ln; Show(s); Out.Ln
END Use;
END RosettaMergeSortUse.
</syntaxhighlight>
Execute: ^Q RosettaMergeSortUse.Use
{{out}}
<pre>
Before:
"A quick brown fox jumps over the lazy dog"
After Asc:
" Aabcdeefghijklmnoooopqrrstuuvwxyz"
After Bad:
" aAbcdeefghijklmnoooopqrrstuuvwxyz"
After Desc:
"zyxwvuutsrrqpoooonmlkjihgfeedcbaA "
</pre>
=={{header|Crystal}}==
{{trans|Ruby}}
<
return a if a.size <= 1
m = a.size // 2
Line 2,248 ⟶ 3,082:
a = [7, 6, 5, 9, 8, 4, 3, 1, 2, 0]
puts merge_sort(a) # => [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]</
=={{header|Curry}}==
Copied from [http://www.informatik.uni-kiel.de/~curry/examples/ Curry: Example Programs]
<
-- and second half of the list
Line 2,281 ⟶ 3,115:
goal1 xs = sort intMerge [3,1,2] xs
goal2 xs = sort intMerge [3,1,2,5,4,8] xs
goal3 xs = sort intMerge [3,1,2,5,4,8,6,7,2,9,1,4,3] xs</
=={{header|D}}==
Arrays only, not in-place.
<
T[] mergeSorted(T)(in T[] D) /*pure nothrow @safe*/ {
Line 2,296 ⟶ 3,130:
void main() {
[3, 4, 2, 5, 1, 6].mergeSorted.writeln;
}</
===Alternative Version===
Line 2,302 ⟶ 3,136:
making life easier for the garbage collector,
but with risk of stack overflow (same output):
<
std.range;
Line 2,320 ⟶ 3,154:
a.mergeSort();
writeln(a);
}</
<!-- Missing in-place version for arrays -->
<!-- Missing generic version for Ranges -->
=={{header|Dart}}==
<
MergeSortInDart sampleSort = MergeSortInDart();
Line 2,442 ⟶ 3,276:
sortedList = sortThisList;
}
}</
=={{header|Delphi}}==
See [https://rosettacode.org/wiki/Sorting_algorithms/Merge_sort#Pascal Pascal].
=={{header|E}}==
<
var result := []
while (xs =~ [x] + xr && ys =~ [y] + yr) {
Line 2,465 ⟶ 3,299:
return merge(sort(list.run(0, split)),
sort(list.run(split)))
}</
=={{header|EasyLang}}==
<syntaxhighlight lang="text">
proc sort . d[] .
while sz < len d[]
swap tmp[] d[]
while left < len d[]
# merge
.
right = len d[]
r = mid + 1
for i = left to right
if r > right or l <= mid and tmp[l] < tmp[r]
d[i] = tmp[l]
l += 1
else
d[i] = tmp[r]
r += 1
.
data[] = [ 29 4 72 44 55 26 27 77 92 5 ]
print data[]
</syntaxhighlight>
=={{header|Eiffel}}==
<syntaxhighlight lang="eiffel">
class
MERGE_SORT [G -> COMPARABLE]
Line 2,630 ⟶ 3,463:
end
</syntaxhighlight>
Test:
<syntaxhighlight lang="eiffel">
class
APPLICATION
Line 2,664 ⟶ 3,497:
end
</syntaxhighlight>
{{out}}
<pre>
Line 2,674 ⟶ 3,507:
=={{header|Elixir}}==
<
def merge_sort(list) when length(list) <= 1, do: list
def merge_sort(list) do
Line 2,680 ⟶ 3,513:
:lists.merge( merge_sort(left), merge_sort(right))
end
end</
Example:
<pre>
Line 2,691 ⟶ 3,524:
Single-threaded version:
<
mergeSort(L) when length(L) > 1 ->
{L1, L2} = lists:split(length(L) div 2, L),
lists:merge(mergeSort(L1), mergeSort(L2)).</
Multi-process version:
<
pMergeSort(L) when length(L) > 1 ->
{L1, L2} = lists:split(length(L) div 2, L),
Line 2,709 ⟶ 3,542:
spawn(mergesort, pMergeSort2, [L1, self()]),
spawn(mergesort, pMergeSort2, [L2, self()]),
Parent ! mergeResults([]).</
another multi-process version (number of processes == number of processor cores):
<
merge_sort(List) -> m(List, erlang:system_info(schedulers)).
Line 2,734 ⟶ 3,567:
after 5000 -> receive_results(Ref, L1, L2)
end.
</syntaxhighlight>
=={{header|ERRE}}==
<syntaxhighlight lang="erre">
PROGRAM MERGESORT_DEMO
Line 2,830 ⟶ 3,663:
PRINT
END PROGRAM
</syntaxhighlight>
=={{header|Euphoria}}==
<
sequence result
result = {}
Line 2,869 ⟶ 3,702:
constant s = rand(repeat(1000,10))
? s
? mergesort(s)</
{{out}}
<pre>{385,599,284,650,457,804,724,300,434,722}
Line 2,876 ⟶ 3,709:
=={{header|F Sharp|F#}}==
<
let rec aux l acc1 acc2 =
match l with
Line 2,897 ⟶ 3,730:
| [x] -> [x]
| _ -> let (l1,l2) = split list
in merge (mergesort l1) (mergesort l2)</
=={{header|Factor}}==
<
2dup [ first ] bi@ <
[ [ [ first ] [ rest-slice ] bi [ suffix ] dip ] dip ]
Line 2,915 ⟶ 3,748:
dup length 1 >
[ dup length 2 / floor [ head ] [ tail ] 2bi [ mergesort ] bi@ merge ]
[ ] if ;</
<
{ 1 2 3 4 5 6 7 }</
=={{header|Forth}}==
This is an in-place mergesort which works on arrays of integers.
<
over @ over @ < if
over @ >r
Line 2,944 ⟶ 3,777:
: .array ( addr len -- ) 0 do dup i cells + @ . loop drop ;
test 10 2dup sort .array \ 0 1 2 3 4 5 6 7 8 9</
=={{header|Fortran}}==
{{works with|Fortran|95 and later and with both free or fixed form syntax.}}
<
implicit none
integer, parameter :: N = 8
Line 3,016 ⟶ 3,849:
end subroutine MergeSort
end program TestMergeSort
</syntaxhighlight>
=={{header|FreeBASIC}}==
Uses 'top down' C-like algorithm in Wikipedia article:
<
Sub copyArray(a() As Integer, iBegin As Integer, iEnd As Integer, b() As Integer)
Line 3,093 ⟶ 3,926:
Print
Print "Press any key to quit"
Sleep</
{{out}}
Line 3,105 ⟶ 3,938:
=={{header|FunL}}==
<
sort( [] ) = []
sort( [x] ) = [x]
Line 3,119 ⟶ 3,952:
println( sort([94, 37, 16, 56, 72, 48, 17, 27, 58, 67]) )
println( sort(['Sofía', 'Alysha', 'Sophia', 'Maya', 'Emma', 'Olivia', 'Emily']) )</
{{out}}
Line 3,129 ⟶ 3,962:
=={{header|Go}}==
<
import "fmt"
Line 3,172 ⟶ 4,005:
}
return
}</
=={{header|Groovy}}==
This is the standard algorithm, except that in the looping phase of the merge we work backwards through the left and right lists to construct the merged list, to take advantage of the [[Groovy]] ''List.pop()'' method. However, this results in a partially merged list in reverse sort order; so we then reverse it to put in back into correct order. This could play havoc with the sort stability, but we compensate by picking aggressively from the right list (ties go to the right), rather than aggressively from the left as is done in the standard algorithm.
<
List mergeList = []
while (left && right) {
Line 3,201 ⟶ 4,034:
merge(left, right)
}</
Test:
<
println (mergeSort([88,18,31,44,4,0,8,81,14,78,20,76,84,33,73,75,82,5,62,70,12,7,1]))
println ()
Line 3,211 ⟶ 4,044:
println (mergeSort([10.0, 10.00, 10, 1]))
println (mergeSort([10.00, 10, 10.0, 1]))
println (mergeSort([10.00, 10.0, 10, 1]))</
The presence of decimal and integer versions of the same numbers, demonstrates, but of course does not '''prove''', that the sort remains stable.
{{out}}
Line 3,227 ⟶ 4,060:
It is possible to write a version based on tail recursion, similar to that written in Haskell, OCaml or F#.
This version also takes into account stack overflow problems induced by recursion for large lists using closure trampolines:
<
list.collate((list.size()+1)/2 as int)
}
Line 3,246 ⟶ 4,079:
assert mergesort([5,4,6,3,1,2]) == [1,2,3,4,5,6]
assert mergesort([3,3,1,4,6,78,9,1,3,5]) == [1,1,3,3,3,4,5,6,9,78]
</syntaxhighlight>
which uses <code>List.collate()</code>, alternatively one could write a purely recursive <code>split()</code> closure as:
<
split = { list, left=[], right=[] ->
if(list.size() <2) [list+left, right]
else split.trampoline(list.tail().tail(), [list.head()]+left,[list.tail().head()]+right)
}.trampoline()
</syntaxhighlight>
=={{header|Haskell}}==
Splitting in half in the middle like the normal merge sort does would be inefficient on the singly-linked lists used in Haskell (since you would have to do one pass just to determine the length, and then another half-pass to do the splitting). Instead, the algorithm here splits the list in half in a different way -- by alternately assigning elements to one list and the other. That way we (lazily) construct both sublists in parallel as we traverse the original list. Unfortunately, under this way of splitting we cannot do a stable sort.
<
merge xs [] = xs
merge xs@(x:xt) ys@(y:yt) | x <= y = x : merge xt ys
Line 3,270 ⟶ 4,103:
mergeSort [x] = [x]
mergeSort xs = let (as,bs) = split xs
in merge (mergeSort as) (mergeSort bs)</
Alternatively, we can use bottom-up mergesort. This starts with lots of tiny sorted lists, and repeatedly merges pairs of them, building a larger and larger sorted list
<
mergePairs sorteds = sorteds
Line 3,278 ⟶ 4,111:
mergeAll [sorted] = sorted
mergeAll sorteds = mergeAll (mergePairs sorteds)</
The standard library's sort function in GHC takes a similar approach to the bottom-up code, the differece being that, instead of starting with lists of size one, which are sorted by default, it detects runs in original list and uses those:
<
sortBy cmp = mergeAll . sequences
where
Line 3,294 ⟶ 4,127:
ascending a as (b:bs)
| a `cmp` b /= GT = ascending b (\ys -> as (a:ys)) bs
ascending a as bs = as [a]: sequences bs</
In this code, mergeAll, mergePairs, and merge are as above, except using the specialized cmp function in merge.
=={{header|Icon}} and {{header|Unicon}}==
<
demosort(mergesort,[3, 14, 1, 5, 9, 2, 6, 3],"qwerty")
end
Line 3,346 ⟶ 4,179:
return X
end</
Note: This example relies on [[Sorting_algorithms/Bubble_sort#Icon| the supporting procedures 'sortop', and 'demosort' in Bubble Sort]].
Line 3,360 ⟶ 4,193:
=={{header|Io}}==
<
merge := method(lst1, lst2,
result := list()
Line 3,387 ⟶ 4,220:
lst := list(9, 5, 3, -1, 15, -2)
lst mergeSort println # ==> list(-2, -1, 3, 5, 9, 15)
lst mergeSortInPlace println # ==> list(-2, -1, 3, 5, 9, 15)</
=={{header|Isabelle}}==
<
imports Main
begin
Line 3,487 ⟶ 4,320:
[0, 1, 3, 3, 5, 9, 32, 33, 42, 67]" by simp
end
</syntaxhighlight>
=={{header|J}}==
{{eff note|J|/:~}}
'''Recursive Solution'''
<syntaxhighlight lang="j">mergesort=: {{
if. 2>#y do. y return.end.
middle=. <.-:#y
X=. mergesort middle{.y
Y=. mergesort middle}.y
X merge Y
}}
merge=: {{ r=. y#~ i=. j=. 0
while. (i<#x)*(j<#y) do. a=. i{x [b=. j{y
if. a<b do. r=. r,a [i=. i+1
end.
if. i<#x do. r=. r, i}.x end.
if. j<#y do. r=. r, j}.y end.
}}</syntaxhighlight>
'''Non-Recursive Solution'''
(This uses the same merge):
<syntaxhighlight lang="j">mergesort=: {{ r=. y [ stride=. 1
while. stride < #r do. stride=. 2*mid=. stride
r=. ;(-stride) (mid&}. <@merge (mid<.#) {.])\ r
end.
}}</syntaxhighlight>
Example use:
<syntaxhighlight lang="j"> mergesort 18 2 8 1 5 14 9 19 11 13 16 0 3 10 17 15 12 4 7 6
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19</syntaxhighlight>
But use J's /:~ if you really need this function.
<syntaxhighlight lang="j"> (/:~ -: mergesort) ?~?10000
1</syntaxhighlight>
'''Tacit Recursive Solution'''
<syntaxhighlight lang="j">case=. (0 = # x=. @:[) + 2 * (0 = # y=. @:])
merge=. ({.x , }.x $: ])`(({.y , }.y $: [))@.({.x > {.y)`]`[@.case
mergesort=. (<. o -: o # ($: o {. merge $: (o=. @:) }.) ]) ^:(1 < #)</syntaxhighlight>
Example use:
<syntaxhighlight lang="j"> mergesort 18 2 8 1 5 14 9 19 11 13 16 0 3 10 17 15 12 4 7 6
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19</syntaxhighlight>
=={{header|Java}}==
{{works with|Java|1.5+}}
<
import java.util.ArrayList;
import java.util.Iterator;
Line 3,571 ⟶ 4,426:
return result;
}
}</
=={{header|JavaScript}}==
<syntaxhighlight lang
function mergeSort(v) {
if (v.length <= 1) {
return v;
}
let m = Math.floor(v.length / 2);
let l = mergeSort(v.slice(0, m));
let r = mergeSort(v.slice(m));
return merge(l, r);
function merge(a, b) {
let i = 0, j = 0;
let n = a.length + b.length;
let c = [];
while (c.length < n) {
if (i < a.length && (j >= b.length || a[i] < b[j])) {
c.push(a[i++]);
} else {
c.push(b[j++]);
}
}
return c;
}
}
function mergeSortInPlace(v) {
if (v.length <= 1) {
return;
}
let m = Math.floor(v.length / 2);
let l = v.slice(0, m);
let r = v.slice(m);
mergeSortInPlace(l);
mergeSortInPlace(r);
merge(l, r, v);
// merge a + b -> c
function merge(a, b, c) {
let i = 0, j = 0;
for (let k = 0; k < c.length; k++) {
if (i < a.length && (j >= b.length || a[i] < b[j])) {
c[k] = a[i++];
} else {
c[k] = b[j++];
}
}
}
}
// even faster
function mergeSortInPlaceFast(v) {
sort(v, 0, v.length, v.slice());
function sort(v, lo, hi, t) {
let n = hi - lo;
if (n <= 1) {
return;
}
let mid = lo + Math.floor(n / 2);
sort(v, lo, mid, t);
sort(v, mid, hi, t);
for (let i = lo; i < hi; i++) {
t[i] = v[i];
}
let i = lo, j = mid;
for (let k = lo; k < hi; k++) {
if (i < mid && (j >= hi || t[i] < t[j])) {
v[k] = t[i++];
} else {
v[k] = t[j++];
}
}
}
}
</syntaxhighlight>
<syntaxhighlight lang="javascript">function merge(left, right, arr) {
var a = 0;
Line 3,620 ⟶ 4,553:
a[ia++] = right[ir++]
}
</syntaxhighlight>
=={{header|jq}}==
The sort function defined here will sort any JSON array.
<
# If x and y are sorted as by "sort", then the result will also be sorted:
def merge:
Line 3,645 ⟶ 4,578:
| . as $in
| [ ($in[0:$len] | merge_sort), ($in[$len:] | merge_sort) ] | merge
end;</
'''Example''':
<syntaxhighlight lang="jq">
( [1, 3, 8, 9, 0, 0, 8, 7, 1, 6],
[170, 45, 75, 90, 2, 24, 802, 66],
[170, 45, 75, 90, 2, 24, -802, -66] )
| (merge_sort == sort)</
{{Out}}
true
Line 3,658 ⟶ 4,591:
=={{header|Julia}}==
<syntaxhighlight lang="julia">function mergesort(arr::Vector)
if length(arr) ≤ 1 return arr end
mid = length(arr) ÷ 2
Line 3,678 ⟶ 4,609:
end
if li ≤ length(lpart)
else
end
return rst
Line 3,686 ⟶ 4,617:
v = rand(-10:10, 10)
println("# unordered: $v\n -> ordered: ", mergesort(v))</
{{out}}
Line 3,693 ⟶ 4,624:
=={{header|Kotlin}}==
<
if (list.size <= 1) {
return list
Line 3,742 ⟶ 4,673:
println("Unsorted: $numbers")
println("Sorted: ${mergeSort(numbers)}")
}</
{{out}}
Line 3,751 ⟶ 4,682:
A close translation from Picolisp. In lambdatalk lists are implemented as dynamical arrays with list-like functions, cons is A.addfirst!, car is A.first, cdr is A.rest, nil is A.new and so on.
<
{def alt
{lambda {:list}
Line 3,779 ⟶ 4,710:
{mergesort {A.new 8 1 5 3 9 0 2 7 6 4}}
-> [0,1,2,3,4,5,6,7,8,9]
</syntaxhighlight>
=={{header|Liberty BASIC}}==
<
dim A(itemCount)
dim tmp(itemCount) 'merge sort needs additionally same amount of storage
Line 3,851 ⟶ 4,782:
next i
print
end sub</
=={{header|Logo}}==
{{works with|UCB Logo}}
<
if :size < 1 [output list :front :list]
output split :size-1 (lput first :list :front) (butfirst :list)
Line 3,871 ⟶ 4,802:
if empty? first :half [output :list]
output merge mergesort first :half mergesort last :half
end</
=={{header|Logtalk}}==
<
msort([X], [X]) :- !.
msort([X, Y| Xs], Ys) :-
Line 3,893 ⟶ 4,824:
merge([X | Xs], Ys, Zs).
merge([], Xs, Xs) :- !.
merge(Xs, [], Xs).</
=={{header|Lua}}==
<
while left_container_begin <= left_container_end do
if right_container_begin > right_container_end then
Line 3,951 ⟶ 4,882:
mergesort_impl(container, 1, #container, comparator)
end</
<
local i,j=1,1
return function()
Line 3,974 ⟶ 4,905:
local s=math.floor(#list/2)
return merge(mergesort{unpack(list,1,s)}, mergesort{unpack(list,s+1)})
end</
=={{header|Lucid}}==
[http://i.csc.uvic.ca/home/hei/lup/06.html]
<
where
p = false fby not p;
Line 3,994 ⟶ 4,925:
iseod(xx) then false else xx <= yy fi;
end;
end;</
=={{header|M2000 Interpreter}}==
<syntaxhighlight lang="m2000 interpreter">
module checkit {
\\ merge sort
Line 4,080 ⟶ 5,011:
}
checkit
</syntaxhighlight>
=={{header|Maple}}==
<syntaxhighlight lang="text">merge := proc(arr, left, mid, right)
local i, j, k, n1, n2, L, R;
n1 := mid-left+1:
Line 4,121 ⟶ 5,052:
arr := Array([17,3,72,0,36,2,3,8,40,0]);
mergeSort(arr,1,numelems(arr)):
arr;</
{{Out|Output}}
<pre>[0,0,2,3,3,8,17,36,40,72]</pre>
Line 4,127 ⟶ 5,058:
=={{header|Mathematica}} / {{header|Wolfram Language}}==
{{works with|Mathematica|7.0}}
<
If[Length[m] >= 2,
middle = Ceiling[Length[m]/2];
Line 4,145 ⟶ 5,076:
True, right[[rightIndex++]]],
{Length[left] + Length[right]}]
]</
=={{header|MATLAB}}==
<
if numel(list) <= 1
Line 4,185 ⟶ 5,116:
%end merge
end %if
end %mergeSort</
Sample Usage:
<
ans =
1 2 3 4 5 6</
=={{header|Maxima}}==
<
[c: [ ], i: 1, j: 1, p: length(a), q: length(b)],
while i <= p and j <= q do (
Line 4,215 ⟶ 5,146:
merge(mergesort(a), mergesort(b))
)
)$</
=={{header|MAXScript}}==
<
(
local left = #()
Line 4,272 ⟶ 5,203:
)
return result
)</
Output:
<syntaxhighlight lang="maxscript">
a = for i in 1 to 15 collect random -5 20
#(-3, 13, 2, -2, 13, 9, 17, 7, 16, 19, 0, 0, 20, 18, 1)
mergeSort a
#(-3, -2, 0, 0, 1, 2, 7, 9, 13, 13, 16, 17, 18, 19, 20)
</syntaxhighlight>
=={{header|Mercury}}==
This version of a sort will sort a list of any type for which there is an ordering predicate defined. Both a function form and a predicate form are defined here with the function implemented in terms of the predicate. Some of the ceremony has been elided.
<
:- module merge_sort.
Line 4,330 ⟶ 5,261:
; merge_sort.merge(Xs, [Y|Ys], M0),
M = [X|M0] ).
</syntaxhighlight>
=={{header|Miranda}}==
<syntaxhighlight lang="miranda">main :: [sys_message]
main = [Stdout ("Before: " ++ show testlist ++ "\n"),
Stdout ("After: " ++ show (mergesort testlist) ++ "\n")]
where testlist = [4,65,2,-31,0,99,2,83,782,1]
mergesort :: [*]->[*]
mergesort [] = []
mergesort [x] = [x]
mergesort xs = merge (mergesort l) (mergesort r)
where (l, r) = split [] [] xs
split l r [] = (l,r)
split l r [x] = (x:l,r)
split l r (x:y:xs) = split (x:l) (y:r) xs
merge xs [] = xs
merge [] ys = ys
merge (x:xs) (y:ys) = x:y:merge xs ys, if x<y
= y:x:merge xs ys, if x>=y</syntaxhighlight>
{{out}}
<pre>Before: [4,65,2,-31,0,99,2,83,782,1]
After: [-31,0,1,2,2,83,4,99,65,782]</pre>
=={{header|Modula-2}}==
Line 4,336 ⟶ 5,289:
{{works with|TopSpeed (JPI) Modula-2 under DOSBox-X}}
Divides the input into blocks of 2 entries, and sorts each block by swapping if necessary. Then merges blocks of 2 into blocks of 4, blocks of 4 into blocks of 8, and so on.
<
DEFINITION MODULE MSIterat;
Line 4,342 ⟶ 5,295:
END MSIterat.
</syntaxhighlight>
<
IMPLEMENTATION MODULE MSIterat;
Line 4,426 ⟶ 5,379:
END MSIterat.
</syntaxhighlight>
<
MODULE MSItDemo;
(* Demo of iterative merge sort *)
Line 4,460 ⟶ 5,413:
IO.WrStr( 'After:'); IO.WrLn; Display( arr);
END MSItDemo.
</syntaxhighlight>
{{out}}
<pre>
Line 4,482 ⟶ 5,435:
The method for splitting a linked list is taken from "Merge sort algorithm for a singly linked list" on Techie Delight. Two pointers step through the list, one at twice the speed of the other. When the fast pointer reaches the end, the slow pointer marks the halfway point.
<
DEFINITION MODULE MergSort;
Line 4,503 ⟶ 5,456:
*)
END MergSort.
</syntaxhighlight>
<
IMPLEMENTATION MODULE MergSort;
Line 4,560 ⟶ 5,513:
END DoMergeSort;
END MergSort.
</syntaxhighlight>
<
MODULE MergDemo;
Line 4,637 ⟶ 5,590:
Display( start);
END MergDemo.
</syntaxhighlight>
{{out}}
<pre>
Line 4,656 ⟶ 5,609:
=={{header|Nemerle}}==
This is a translation of a Standard ML example from [[wp:Standard_ML#Mergesort|Wikipedia]].
<
using System.Console;
using Nemerle.Collections;
Line 4,703 ⟶ 5,656:
WriteLine(test2);
}
}</
{{out}}
<pre>[1, 2, 3, 4, 5, 6, 7, 8, 9]
Line 4,709 ⟶ 5,662:
=={{header|NetRexx}}==
<
options replace format comments java crossref savelog symbols binary
Line 4,792 ⟶ 5,745:
return result
</syntaxhighlight>
{{out}}
<pre>
Line 4,815 ⟶ 5,768:
=={{header|Nim}}==
<
let
leftLen = middle - left
Line 4,866 ⟶ 5,819:
var a = @[4, 65, 2, -31, 0, 99, 2, 83, 782]
mergeSort a
echo a</
{{out}}
<pre>@[-31, 0, 2, 2, 4, 65, 83, 99, 782]</pre>
=={{header|OCaml}}==
<
match n, xs with
0, xs ->
Line 4,891 ⟶ 5,844:
let _ =
merge_sort compare [8;6;4;2;1;3;5;7;9]</
=={{header|Oz}}==
<
fun {MergeSort Xs}
case Xs
Line 4,908 ⟶ 5,861:
end
in
{Show {MergeSort [3 1 4 1 5 9 2 6 5]}}</
=={{header|PARI/GP}}==
Note also that the built-in <code>vecsort</code> and <code>listsort</code> use a merge sort internally.
<
if(#v<2, return(v));
my(m=#v\2,left=vector(m,i,v[i]),right=vector(#v-m,i,v[m+i]));
Line 4,931 ⟶ 5,884:
);
ret
};</
=={{header|Pascal}}==
{{works with|FPC}}
<syntaxhighlight lang="pascal">
program MergeSortDemo;
{$mode objfpc}{$h+}
procedure MergeSort(var A: array of Integer);
var
Buf: array of Integer;
procedure Merge(L, M, R: Integer);
var
begin
J := Succ(M);
if (J > R) or (I <= M) and (A[I] <= A[J]) then begin
end else begin
Buf[K] := A[J];
Inc(J);
end;
Move(Buf[0], A[L], Succ(R - L) * SizeOf(Integer));
end;
procedure MSort(L, R: Integer);
var
begin
if R > L then begin
{$push}{$q-}{$r-}M := (L + R) shr 1;{$pop}
if A[M] > A[M + 1] then
end;
end;
begin
if Length(A) > 1 then begin
SetLength(Buf, Length(A));
MSort(0, High(A));
end;
end;
procedure PrintArray(const Name: string; const A: array of Integer);
var
begin
Write(Name, ': [');
for I := 0 to High(A) - 1 do
Write(A[I], ', ');
WriteLn(A[High(A)], ']');
end;
var
a1: array[-7..5] of Integer = (27, -47, 14, 39, 47, -2, -8, 20, 18, 22, -49, -40, -8);
a2: array of Integer = (9, -25, -16, 24, 39, 42, 20, 20, 39, 10, -47, 28);
begin
PrintArray('a1', a1);
MergeSort(a2);
PrintArray('a2', a2);
end.
</syntaxhighlight>
{{out}}
<pre>
a1: [-49, -47, -40, -8, -8, -2, 14, 18, 20, 22, 27, 39, 47]
a2: [-47, -25, -16, 9, 10, 20, 20, 24, 28, 39, 39, 42]
</pre>
===improvement===
Line 5,035 ⟶ 5,962:
Works with ( Turbo -) Delphi too.
<
{$MODE DELPHI}
{$OPTIMIZATION ON,Regvar,ASMCSE,CSE,PEEPHOLE}
Line 5,234 ⟶ 6,161:
FreeData (Data);
end.
</syntaxhighlight>
;output:
<pre>Free pascal 2.6.4 32bit / Win7 / i 4330 3.5 Ghz
Line 5,244 ⟶ 6,171:
=={{header|Perl}}==
<
my @x = @_;
return @x if @x < 2;
Line 5,261 ⟶ 6,188:
my @a = (4, 65, 2, -31, 0, 99, 83, 782, 1);
@a = merge_sort @a;
print "@a\n";</
Also note, the built-in function [http://perldoc.perl.org/functions/sort.html sort] uses mergesort.
=={{header|Phix}}==
<!--<
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
Line 5,298 ⟶ 6,225:
<span style="color: #0000FF;">?</span> <span style="color: #000000;">s</span>
<span style="color: #0000FF;">?</span> <span style="color: #000000;">mergesort</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">))</span>
<!--</
{{out}}
<pre>
Line 5,306 ⟶ 6,233:
=={{header|PHP}}==
<
if(count($arr) == 1 ) return $arr;
$mid = count($arr) / 2;
Line 5,340 ⟶ 6,267:
$arr = array( 1, 5, 2, 7, 3, 9, 4, 6, 8);
$arr = mergesort($arr);
echo implode(',',$arr);</
{{out}}
<pre>1,2,3,4,5,6,7,8,9</pre>
Line 5,346 ⟶ 6,273:
=={{header|Picat}}==
{{trans|Prolog}}
<
msort([],[]).
msort([X],[X]).
Line 5,371 ⟶ 6,298:
merge([L|LS],[R|RS],[R|T]) :-
L @> R,
merge([L|LS],RS,T).</
=={{header|PicoLisp}}==
PicoLisp's built-in sort routine uses merge sort. This is a high level implementation.
<
(if List (cons (car List) (alt (cddr List))) ()) )
Line 5,391 ⟶ 6,318:
List) )
(mergesort (8 1 5 3 9 0 2 7 6 4))</
=={{header|PL/I}}==
<
/* Merge A(1:LA) with B(1:LB), putting the result in C
Line 5,442 ⟶ 6,369:
CALL MERGE(TP,M,AMP1,N-M,AP);
RETURN;
END MERGESORT;</
=={{header|PowerShell}}==
<syntaxhighlight lang="powershell">
function MergeSort([object[]] $SortInput)
{
Line 5,482 ⟶ 6,409:
$result + $left + $right
}
</syntaxhighlight>
=={{header|Prolog}}==
<
% True if S is a sorted copy of L, using merge sort
msort( [], [] ).
Line 5,502 ⟶ 6,429:
merge( LS, [], LS ).
merge( [L|LS], [R|RS], [L|T] ) :- L =< R, merge( LS, [R|RS], T).
merge( [L|LS], [R|RS], [R|T] ) :- L > R, merge( [L|LS], RS, T).</
=={{header|PureBasic}}==
A non-optimized version with lists.
<
ForEach m()
Print(LSet(Str(m()), 3," "))
Line 5,589 ⟶ 6,516:
Input()
CloseConsole()
EndIf</
{{out|Sample output}}
<pre>22 51 31 59 58 45 11 2 16 56 38 42 2 10 23 41 42 25 45 28 42
Line 5,596 ⟶ 6,523:
=={{header|Python}}==
{{works with|Python|2.6+}}
<
def merge_sort(m):
Line 5,608 ⟶ 6,535:
left = merge_sort(left)
right = merge_sort(right)
return list(merge(left, right))</
Pre-2.6, merge() could be implemented like this:
<
result = []
left_idx, right_idx = 0, 0
Line 5,626 ⟶ 6,553:
if right_idx < len(right):
result.extend(right[right_idx:])
return result</
using only recursions
<
if x==[]: return y
if y==[]: return x
Line 5,639 ⟶ 6,566:
a = list(map(int, input().split()))
print(sort(a, len(a)))</
=={{header|Quackery}}==
<
[ dup [] != while
over [] != while
Line 5,660 ⟶ 6,587:
swap recurse
swap recurse
merge ] is mergesort ( [ --> [ )</
=={{header|R}}==
<
{
merge_ <- function(left, right)
Line 5,702 ⟶ 6,629:
}
}
mergesort(c(4, 65, 2, -31, 0, 99, 83, 782, 1)) # -31 0 1 2 4 65 83 99 782</
=={{header|Racket}}==
<
#lang racket
Line 5,721 ⟶ 6,648:
[_ (define-values (ys zs) (split-at xs (quotient (length xs) 2)))
(merge (merge-sort ys) (merge-sort zs))]))
</syntaxhighlight>
This variation is bottom up:
<
#lang racket
Line 5,743 ⟶ 6,670:
(cond [(<= a b) (cons a (merge as ys))]
[ (cons b (merge xs bs))])])]))
</syntaxhighlight>
=={{header|Raku}}==
<syntaxhighlight lang="raku" line>
#| Recursive, single-thread, mergesort implementation
# recursion step
my @r = samewith @a[ $m ..^ @a ];
# short cut - in case of no overlapping in left and right parts
return flat @l, @r if @l[*-1] !after @r[0];
return flat
# merge step
return flat gather {
take @l[0] before @r[0]
?? @l.shift
!! @r.shift
while @l and @r;
take @l, @r;
}
}</syntaxhighlight>
Some intial testing
<syntaxhighlight lang="raku" line>
my @data = 6, 7, 2, 1, 8, 9, 5, 3, 4;
say 'input = ' ~ @data;
say 'output = ' ~ @data.&merge_sort;</
{{out}}
<pre>input = 6 7 2 1 8 9 5 3 4
output = 1 2 3 4 5 6 7 8 9</pre>
===concurrent implementation===
Let's implement it using parallel sorting.
<syntaxhighlight lang="raku" line>
#| Recursive, naive multi-thread, mergesort implementation
sub mergesort-parallel-naive ( @a ) {
return @a if @a <= 1;
my $m = @a.elems div 2;
# recursion step launching new thread
my @l = start { samewith @a[ 0 ..^ $m ] };
# meanwhile recursively sort right side
my @r = samewith @a[ $m ..^ @a ] ;
# as we went parallel on left side, we need to await the result
await @l[0] andthen @l = @l[0].result;
# short cut - in case of no overlapping left and right parts
return flat @l, @r if @l[*-1] !after @r[0];
return flat @r, @l if @r[*-1] !after @l[0];
# merge step
return flat gather {
take @l[0] before @r[0]
?? @l.shift
!! @r.shift
while @l and @r;
take @l, @r;
}
}
</syntaxhighlight>
and tune the batch size required to launch a new thread.
<syntaxhighlight lang="raku" line>
#| Recursive, batch tuned multi-thread, mergesort implementation
sub mergesort-parallel ( @a, $batch = 2**9 ) {
return @a if @a <= 1;
my $m = @a.elems div 2;
# recursion step
my @l = $m >= $batch
?? start { samewith @a[ 0 ..^ $m ], $batch }
!! samewith @a[ 0 ..^ $m ], $batch ;
# meanwhile recursively sort right side
my @r = samewith @a[ $m ..^ @a ], $batch;
# if we went parallel on left side, we need to await the result
await @l[0] andthen @l = @l[0].result if @l[0] ~~ Promise;
# short cut - in case of no overlapping left and right parts
return flat @l, @r if @l[*-1] !after @r[0];
return flat @r, @l if @r[*-1] !after @l[0];
# merge step
return flat gather {
take @l[0] before @r[0]
?? @l.shift
!! @r.shift
while @l and @r;
take @l, @r;
}
}
</syntaxhighlight>
===testing===
Let's run some tests ...
<syntaxhighlight lang="raku" line>
say "x" x 10 ~ " Testing " ~ "x" x 10;
use Test;
my @functions-under-test = &mergesort, &mergesort-parallel-naive, &mergesort-parallel;
my @testcases =
() => (),
<a>.List => <a>.List,
<a a> => <a a>,
("b", "a", 3) => (3, "a", "b"),
<h b a c d f e g> => <a b c d e f g h>,
<a 🎮 3 z 4 🐧> => <a 🎮 3 z 4 🐧>.sort
;
plan @testcases.elems * @functions-under-test.elems;
for @functions-under-test -> &fun {
say &fun.name;
is-deeply &fun(.key), .value, .key ~ " => " ~ .value for @testcases;
}
done-testing;
</syntaxhighlight>
{{out}}
<pre>xxxxxxxxxx Testing xxxxxxxxxx
1..18
mergesort
ok 1 - =>
ok 2 - a => a
ok 3 - a a => a a
ok 4 - b a 3 => 3 a b
ok 5 - h b a c d f e g => a b c d e f g h
ok 6 - a 🎮 3 z 4 🐧 => 3 4 a z 🎮 🐧
mergesort-parallel-naive
ok 7 - =>
ok 8 - a => a
ok 9 - a a => a a
ok 10 - b a 3 => 3 a b
ok 11 - h b a c d f e g => a b c d e f g h
ok 12 - a 🎮 3 z 4 🐧 => 3 4 a z 🎮 🐧
mergesort-parallel
ok 13 - =>
ok 14 - a => a
ok 15 - a a => a a
ok 16 - b a 3 => 3 a b
ok 17 - h b a c d f e g => a b c d e f g h
ok 18 - a 🎮 3 z 4 🐧 => 3 4 a z 🎮 🐧</pre>
===benchmarking===
and some Benchmarking.
<syntaxhighlight lang="raku" line>
use Benchmark;
my $runs = 5;
my $elems = 10 * Kernel.cpu-cores * 2**10;
my @unsorted of Str = ('a'..'z').roll(8).join xx $elems;
my UInt $l-batch = 2**13;
my UInt $m-batch = 2**11;
my UInt $s-batch = 2**9;
my UInt $t-batch = 2**7;
say "elements: $elems, runs: $runs, cpu-cores: {Kernel.cpu-cores}, large/medium/small/tiny-batch: $l-batch/$m-batch/$s-batch/$t-batch";
my %results = timethese $runs, {
single-thread => { mergesort(@unsorted) },
parallel-naive => { mergesort-parallel-naive(@unsorted) },
parallel-tiny-batch => { mergesort-parallel(@unsorted, $t-batch) },
parallel-small-batch => { mergesort-parallel(@unsorted, $s-batch) },
parallel-medium-batch => { mergesort-parallel(@unsorted, $m-batch) },
parallel-large-batch => { mergesort-parallel(@unsorted, $l-batch) },
}, :statistics;
my @metrics = <mean median sd>;
my $msg-row = "%.4f\t" x @metrics.elems ~ '%s';
say @metrics.join("\t");
for %results.kv -> $name, %m {
say sprintf($msg-row, %m{@metrics}, $name);
}
</syntaxhighlight>
<pre>
elements: 40960, runs: 5, cpu-cores: 4, large/medium/small/tiny-batch: 8192/2048/512/128
mean median sd
7.7683 8.0265 0.5724 parallel-naive
3.1354 3.1272 0.0602 parallel-tiny-batch
2.6932 2.6599 0.1831 parallel-medium-batch
2.8139 2.7832 0.0641 parallel-large-batch
3.0908 3.0593 0.0675 parallel-small-batch
5.9989 5.9450 0.1518 single-thread
</pre>
=={{header|REBOL}}==
Line 5,813 ⟶ 6,916:
a
]</pre>
=={{header|Refal}}==
<syntaxhighlight lang="refal">$ENTRY Go {
, 7 6 5 9 8 4 3 1 2 0: e.Arr
= <Prout e.Arr>
<Prout <Sort e.Arr>>;
};
Sort {
= ;
s.N = s.N;
e.X, <Split e.X>: (e.L) (e.R) = <Merge (<Sort e.L>) (<Sort e.R>)>;
};
Split {
(e.L) (e.R) = (e.L) (e.R);
(e.L) (e.R) s.X = (e.L s.X) (e.R);
(e.L) (e.R) s.X s.Y e.Z = <Split (e.L s.X) (e.R s.Y) e.Z>;
e.X = <Split () () e.X>;
};
Merge {
(e.L) () = e.L;
() (e.R) = e.R;
(s.X e.L) (s.Y e.R), <Compare s.X s.Y>: {
'-' = s.X <Merge (e.L) (s.Y e.R)>;
s.Z = s.Y <Merge (s.X e.L) (e.R)>;
};
};</syntaxhighlight>
{{out}}
<pre>7 6 5 9 8 4 3 1 2 0
0 1 2 3 4 5 6 7 8 9</pre>
=={{header|REXX}}==
Note: the array elements can be anything: integers, floating point (exponentiated), character strings ···
<
call init /*sinfully initialize the @ array. */
call show 'before sort' /*show the "before" array elements. */
Line 5,855 ⟶ 6,990:
else do; !.k= !.j; j= j + 1; end
end /*k*/
return</
{{out|output|text= when using the default input:}}
(Shown at three-quarter size.)
Line 5,882 ⟶ 7,017:
=={{header|Ruby}}==
<
return m if m.length <= 1
Line 5,900 ⟶ 7,035:
ary = [7,6,5,9,8,4,3,1,2,0]
p merge_sort(ary) # => [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]</
Here's a version that monkey patches the Array class, with an example that demonstrates it's a stable sort
<
def mergesort(&comparitor)
return self if length <= 1
Line 5,936 ⟶ 7,071:
# => [["UK", "Birmingham"], ["UK", "London"], ["US", "Birmingham"], ["US", "New York"]]
p ary.mergesort {|a, b| a[1] <=> b[1]}
# => [["US", "Birmingham"], ["UK", "Birmingham"], ["UK", "London"], ["US", "New York"]]</
=={{header|Rust}}==
{{works with|rustc|1.9.0}}
Recursive with buffer equal to the size of the sort vector
<syntaxhighlight lang="rust">
pub fn merge_sort1<T: Copy + Ord>(v: &mut [T]) {
sort(v, &mut Vec::new());
fn sort<T: Copy + Ord>(v: &mut [T], t: &mut Vec<T>) {
0 | 1 => (),
// n if n <= 20 => insertion_sort(v),
n => {
if t.is_empty() {
t.reserve_exact(n);
t.resize(n, v[0]);
}
let m = n / 2;
sort(&mut v[..m], t);
sort(&mut v[m..], t);
if v[m - 1] <= v[m] {
return;
}
copy(v, t);
merge(&t[..m], &t[m..n], v);
}
}
}
// merge a + b -> c
#[inline(always)]
fn merge<T: Copy + Ord>(a: &[T], b: &[T], c: &mut [T]) {
let (mut i, mut j) = (0, 0);
for k in 0..c.len() {
if i < a.len() && (j >= b.len() || a[i] <= b[j]) {
c[k] = a[i];
i += 1;
} else {
c[k] = b[j];
j += 1;
}
}
}
#[inline(always)]
fn copy<T: Copy>(src: &[T], dst: &mut [T]) {
for i in 0..src.len() {
dst[i] = src[i];
}
}
#[inline(always)]
fn insertion_sort<T: Ord>(v: &mut [T]) {
for i in 1..v.len() {
let mut j = i;
while j > 0 && v[j] < v[j - 1] {
v.swap(j, j - 1);
j -= 1;
}
}
}
}
</syntaxhighlight>
Recursive with buffer equal to half the size of the sort vector
<syntaxhighlight lang="rust">
pub fn merge_sort2<T: Copy + Ord>(v: &mut [T]) {
sort(v, &mut Vec::new());
fn sort<T: Copy + Ord>(v: &mut [T], t: &mut Vec<T>) {
match v.len() {
0 | 1 => (),
// n if n <= 20 => insertion_sort(v),
let m = n / 2;
if t.is_empty() {
t.reserve_exact(m);
t.resize(m, v[0]);
}
if v[m - 1] <= v[m] {
return;
}
merge(&t[..m], v);
}
}
}
// merge a + b[a.len..] -> b
#[inline(always)]
fn merge<T: Copy + Ord>(a: &[T], b: &mut [T]) {
let (mut i, mut j) = (0, a.len());
for k in 0..b.len() {
if i < a.len() && (j >= b.len() || a[i] <= b[j]) {
b[k] = a[i];
i += 1;
} else {
b[k] = b[j];
j += 1;
}
}
}
#[inline(always)]
fn copy<T: Copy>(src: &[T], dst: &mut [T]) {
for i in 0..src.len() {
dst[i] = src[i];
}
}
}
</syntaxhighlight>
Version without recursion call
<
pub fn
0 | 1 => (),
let mut t = Vec::with_capacity(n);
t.resize(n, v[0]);
let mut p = 1;
p = merge_blocks(v, &mut t, p, n);
copy(&t, v);
return;
}
p = merge_blocks(&t, v, p, n);
}
}
}
#[inline(always)]
fn merge_blocks<T: Copy + Ord>(a: &[T], b: &mut [T], p: usize, n: usize) -> usize {
let mut i = 0;
while i < n {
copy(&a[i..], &mut b[i..])
} else if i + p * 2 > n {
merge(&a[i..i + p], &a[i + p..], &mut b[i..]);
} else {
merge(&a[i..i + p], &a[i + p..i + p * 2], &mut b[i..i + p * 2]);
}
i += p * 2;
p * 2
}
// merge a + b -> c
#[inline(always)]
fn merge<T: Copy + Ord>(a: &[T], b: &[T], c: &mut [T]) {
let (mut i, mut j, mut k) = (0, 0, 0);
while i < a.len() && j < b.len() {
if a[i] < b[j] {
c[k] = a[i];
i += 1;
} else {
c[k] = b[j];
j += 1;
}
k += 1;
}
if i < a.len() {
copy(&a[i..], &mut c[k..]);
}
if j < b.len() {
copy(&b[j..], &mut c[k..]);
}
}
#[inline(always)]
fn copy<T: Copy>(src: &[T], dst: &mut [T]) {
for i in 0..src.len() {
dst[i] = src[i];
}
}
}
</syntaxhighlight>
=={{header|Scala}}==
Line 6,030 ⟶ 7,256:
tail recursion, which would typically require reversing the result, as well as being
a bit more convoluted.
<
import scala.language.implicitConversions
Line 6,054 ⟶ 7,280:
}
</syntaxhighlight>
=={{header|Scheme}}==
<
(define (merge left right)
(cond
Line 6,079 ⟶ 7,305:
l
(merge (merge-sort (take l half) gt?)
(merge-sort (list-tail l half) gt?)))))</
(merge-sort '(1 3 5 7 9 8 6 4 2) >)
=={{header|Seed7}}==
<
local
var integer: mid is 0;
Line 6,118 ⟶ 7,344:
scratch := length(arr) times elemType.value;
mergeSort2(arr, 1, length(arr), scratch);
end func;</
Original source: [http://seed7.sourceforge.net/algorith/sorting.htm#mergeSort2]
=={{header|SETL}}==
<syntaxhighlight lang="setl">program merge_sort;
test := [-8, 241, 9, 316, -6, 3, 413, 9, 10];
print(test, '=>', mergesort(test));
proc mergesort(m);
if #m <= 1 then
return m;
end if;
middle := #m div 2;
left := mergesort(m(..middle));
right := mergesort(m(middle+1..));
if left(#left) <= right(1) then
return left + right;
end if;
return merge(left, right);
end proc;
proc merge(left, right);
result := [];
loop while left /= [] and right /= [] do
if left(1) <= right(1) then
item fromb left;
else
item fromb right;
end if;
result with:= item;
end loop;
return result + left + right;
end proc;
end program;</syntaxhighlight>
{{out}}
<pre>[-8 241 9 316 -6 3 413 9 10] => [-8 -6 3 9 9 10 241 316 413]</pre>
=={{header|Sidef}}==
<
var result = []
while (left && right) {
Line 6,148 ⟶ 7,409:
# String sort
var strings = rand('a'..'z', 10)
say mergesort(strings)</
=={{header|Standard ML}}==
<
| merge cmp (xs, []) = xs
| merge cmp (xs as x::xs', ys as y::ys') =
case cmp (x, y) of
| _ => x :: merge cmp (xs', ys)
fun merge_sort cmp [] = []
| merge_sort cmp [x] = [x]
Line 6,164 ⟶ 7,426:
in
merge cmp (merge_sort cmp ys, merge_sort cmp zs)
end</syntaxhighlight>
{{out|Poly/ML}}
<pre>
> merge_sort Int.compare [8,6,4,2,1,3,5,7,9];
val it = [1, 2, 3, 4, 5, 6, 7, 8, 9]: int list
> merge_sort String.compare ["Plum", "Pear", "Peach", "Each"];
val it = ["Each", "Peach", "Pear", "Plum"]: string list
>
</syntaxhighlight>
=={{header|Swift}}==
<
// Source: https://github.com/raywenderlich/swift-algorithm-club/tree/master/Merge%20Sort
// NOTE: by use of generics you can make it sort arrays of any type that conforms to
Line 6,220 ⟶ 7,488:
return merge(left: leftPart, right: rightPart)
}</
=={{header|Tailspin}}==
The standard recursive merge sort
<
templates mergesort
templates merge
@: $(2);
[ $(1)... ->
when
|
otherwise
^@(1)
end merge
$ -> #
Line 6,247 ⟶ 7,514:
[4,5,3,8,1,2,6,7,9,8,5] -> mergesort -> !OUT::write
</syntaxhighlight>
{{out}}
<pre>
Line 6,254 ⟶ 7,521:
A little different spin where the array is first split into a list of single-element lists and then merged.
<
templates mergesort
templates merge
Line 6,290 ⟶ 7,557:
[4,5,3,8,1,2,6,7,9,8,5] -> mergesort -> !OUT::write
</syntaxhighlight>
{{out}}
<pre>
Line 6,297 ⟶ 7,564:
=={{header|Tcl}}==
<
proc mergesort m {
Line 6,329 ⟶ 7,596:
}
puts [mergesort {8 6 4 2 1 3 5 7 9}] ;# => 1 2 3 4 5 6 7 8 9</
Also note that Tcl's built-in <tt>lsort</tt> command uses the mergesort algorithm.
=={{header|Unison}}==
<
mergeSortBy cmp =
merge l1 l2 =
Line 6,346 ⟶ 7,613:
lst ->
match halve lst with
(left, right) -> merge (mergeSortBy cmp left) (mergeSortBy cmp right)</
=={{header|UnixPipes}}==
{{works with|Zsh}}
<
(while read a b ; do
echo $a > $1 ; echo $b > $2
Line 6,365 ⟶ 7,632:
}
cat to.sort | mergesort</
=={{header|Ursala}}==
<
mergesort "p" = @iNCS :-0 ~&B^?a\~&YaO "p"?abh/~&alh2faltPrXPRC ~&arh2falrtPXPRC
Line 6,374 ⟶ 7,641:
#show+
example = mergesort(lleq) <'zoh','zpb','hhh','egi','bff','cii','yid'></
{{out}}
<pre>
Line 6,385 ⟶ 7,652:
zpb</pre>
The mergesort function could also have been defined using the built in sorting operator, -<, because the same algorithm is used.
<
=={{header|V}}==
merge uses the helper mergei to merge two lists. The mergei takes a stack of the form [mergedlist] [list1] [list2]
it then extracts one element from list2, splits the list1 with it, joins the older merged list, first part of list1 and the element that was used for splitting (taken from list2) into the new merged list. the new list1 is the second part of the split on older list1. new list2 is the list remaining after the element e2 was extracted from it.
<
[mergei
uncons [swap [>] split] dip
Line 6,407 ⟶ 7,674:
[splitarr]
[merge]
binrec].</
[8 7 6 5 4 2 1 3 9] msort puts
=={{header|V (Vlang)}}==
<syntaxhighlight lang="v (vlang)">fn main() {
mut a := [170, 45, 75, -90, -802, 24, 2, 66]
println("before: $a")
Line 6,452 ⟶ 7,719:
}
return result
}</
=={{header|Wren}}==
<
var result = []
while (left.count > 0 && right.count > 0) {
Line 6,487 ⟶ 7,754:
}
var
for (a in
System.print("Before: %(a)")
a = mergeSort.call(a)
System.print("After : %(a)")
System.print()
}</
{{out}}
Line 6,506 ⟶ 7,773:
Alternatively we can just call a library method.
{{libheader|Wren-sort}}
<
var
for (a in
System.print("Before: %(a)")
a = Sort.merge(a)
System.print("After : %(a)")
System.print()
}</
{{out}}
Line 6,524 ⟶ 7,791:
This is based on an example in "Fundamentals of Computer Algorithms" by
Horowitz & Sahni.
<
proc MergeSort(A, Low, High); \Sort array A from Low to High
Line 6,549 ⟶ 7,816:
MergeSort(A, 0, 10-1);
for I:= 0 to 10-1 do [IntOut(0, A(I)); ChOut(0, ^ )];
]</
{{out}}
Line 6,561 ⟶ 7,828:
=={{header|Yabasic}}==
{{trans|FreeBASIC}}
<
dim b(9)
Line 6,650 ⟶ 7,917:
printArray(a2())
end
</syntaxhighlight>
Line 6,658 ⟶ 7,925:
This is a bottom up version of merge sort:
<
comment:
#true
Line 6,743 ⟶ 8,010:
(sort11) comparator
(cons) (merge) comparator (car) jumble (002) "cadr" jumble
(sort11) comparator (002) "cddr" jumble</
=={{header|zkl}}==
Pretty wasteful memory wise, probably not suitable for large sorts.
{{trans|Clojure}}
<
if (not left) return(right);
if (not right) return(left);
Line 6,760 ⟶ 8,027:
n:=L.len()/2;
return(_merge(self.fcn(L[0,n]), self.fcn(L[n,*])));
}</
<
merge_sort("big fjords vex quick waltz nymph").concat().println();</
{{out}}
<pre>
Line 6,769 ⟶ 8,036:
</pre>
Or, for lists only:
<
if (L.len()<2) return(L.copy());
n:=L.len()/2;
self.fcn(L[0,n]).merge(self.fcn(L[n,*]));
}</
<
mergeSort("big fjords vex quick waltz nymph".split("")).concat().println();</
{{out}}
<pre>
| |||