Sorting algorithms/Merge sort: Difference between revisions

 

'''function''' ''mergesort''(m)

'''var''' list left, right, result

'''return''' result

 

 

=={{header|ActionScript}}==

{

//Arrays of length 1 and 0 are always sorted

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 (<>);

package Mergesort is

function Sort(Item : Collection_Type) return Collection_Type;

 

-----------

end Sort;

 

The following code provides an usage example for the generic package defined above.

with Mergesort;

 

Print(List);

Print(List_Sort.Sort(List));

<pre>

1 5 2 7 3 9 4 6

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: (

 

[32]CHAR char array data := "big fjords vex quick waltz nymph";

abcdefghiijklmnopqrstuvwxyz

Optimised version:

# 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

 

[]REF CHAR result = opt merge sort(data);

abcdefghiijklmnopqrstuvwxyz

=={{header|AutoHotkey}}==

MsgBox % MSort("xxx")

MsgBox % MSort("3,2,1")

}

}

 

=={{header|C}}==

#include <stdlib.h>

#include <string.h>

 

 

}

}

 

 

 

 

 

 

}

 

=={{header|C++}}==

#include <algorithm> // for std::inplace_merge

#include <functional> // for std::less

{

mergesort(first, last, std::less<typename std::iterator_traits<RandomAccessIterator>::value_type>());

 

 

 

 

 

 

 

 

 

 

 

 

=={{header|Common Lisp}}==

(let ((split (floor (length sequence) 2)))

(if (zerop split)

(merge result-type (merge-sort result-type (subseq sequence 0 split) predicate)

(merge-sort result-type (subseq sequence split) predicate)

 

<tt>merge</tt> is a standard Common Lisp function.

> (merge-sort 'list (list 1 3 5 7 9 8 6 4 2) #'<)

(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

 

goal1 xs = sort intMerge [3,1,2] xs

goal2 xs = sort intMerge [3,1,2,5,4,8] xs

=={{header|D}}==

Arrays only, not in-place.

 

}

 

void main() {

auto a = [3, 4, 2, 5, 1, 6];

<!-- Missing in-place version for arrays -->

<!-- Missing generic version for Ranges -->

 

 

var result := []

while (xs =~ [x] + xr && ys =~ [y] + yr) {

return merge(sort(list.run(0, split)),

sort(list.run(split)))

 

=={{header|Erlang}}==

 

Single-threaded version:

mergeSort(L) when length(L) > 1 ->

{L1, L2} = lists:split(length(L) div 2, L),

 

Multi-process version:

pMergeSort(L) when length(L) > 1 ->

{L1, L2} = lists:split(length(L) div 2, L),

spawn(mergesort, pMergeSort2, [L1, self()]),

spawn(mergesort, pMergeSort2, [L2, self()]),

 

=={{header|F Sharp|F#}}==

let rec aux l acc1 acc2 =

match l with

| ([],y) -> y

| (x::tx,y::ty) ->

else y::merge l1 ty

let rec mergesort list =

| [x] -> [x]

| _ -> let (l1,l2) = split list

 

=={{header|Forth}}==

This is an in-place mergesort which works on arrays of integers.

over @ over @ < if

over @ >r

: .array ( addr len -- ) 0 do dup i cells + @ . loop drop ;

 

 

=={{header|Fortran}}==