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) |
|||
| (35 intermediate revisions by 10 users not shown) | |||
Line 1,234:
.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}}==
<syntaxhighlight lang="python">fun mergesort(m):
Line 1,868 ⟶ 1,935:
END</syntaxhighlight>
==={{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}}==
Line 2,547 ⟶ 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}}==
Line 2,789 ⟶ 3,304:
<syntaxhighlight lang="text">
len tmp[] len d[]
sz = 1
while sz < len d[]
swap tmp[] d[]
left = 1
while left < len d[]
# merge
mid = left + sz - 1
if mid > len d[]
mid = len d[]
.
right = mid + sz
if right > len d[]
right = len d[]
.
l = left
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
.
.
left += 2 * sz
.
.
data[] = [ 29 4 72 44 55 26 27 77 92 5 ]
print data[]
</syntaxhighlight>
Line 3,845 ⟶ 4,360:
<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}}==
Line 4,067 ⟶ 4,591:
=={{header|Julia}}==
<syntaxhighlight lang="julia">function mergesort(arr::Vector)
if length(arr) ≤ 1 return arr end
Line 4,087 ⟶ 4,609:
end
if li ≤ length(lpart)
else
end
return rst
Line 4,740 ⟶ 5,262:
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 6,129 ⟶ 6,673:
=={{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;
Line 6,151 ⟶ 6,706:
<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 6,196 ⟶ 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}}==
Line 6,594 ⟶ 7,346:
end func;</syntaxhighlight>
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}}==
Line 6,628 ⟶ 7,415:
| 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,638 ⟶ 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}}==
Line 6,702 ⟶ 7,496:
templates merge
@: $(2);
[ $(1)... ->
when
|
otherwise
^@(1)
end merge
$ -> #
Line 6,929 ⟶ 7,722:
=={{header|Wren}}==
<syntaxhighlight lang="
var result = []
while (left.count > 0 && right.count > 0) {
Line 6,961 ⟶ 7,754:
}
var
for (a in
System.print("Before: %(a)")
a = mergeSort.call(a)
Line 6,980 ⟶ 7,773:
Alternatively we can just call a library method.
{{libheader|Wren-sort}}
<syntaxhighlight lang="
var
for (a in
System.print("Before: %(a)")
a = Sort.merge(a)
| |||