Aai wrote:
>
> For those interested (if not for a RC contribution then for the problem
> itself).
>
> The merge sort task is still open (I wonder why: ok it's ridiculous to use
> something else as /:~ y).
>
Aai,
It's not always ridiculous---for example, merging two sorted arrays of total
length n into a sorted array merge does in O(n) while /:~ in O(n log n).
Common
LISP has both sort and merge, and I've come to appreciate the difference
between
the two very much when merging several fairly large sorted data sets, so
much
that I would be very happy to see merge built-in in J.
Anyhow, back to your program:
> For a start, here's my translation of the Haskell contribution.
>
> merge =: ({...@] , ($: }.)) `({...@[ , ($: }.)~) @. (<:&{.) ` , @. (+.&(0=#))
> split =: </.~ 0 1$~#
> mergeSort =: merge & $: &>/@ split ` ] @. (1>:#)
> [...]
>
If we note that
({...@[ , ($: }.)~) === ({...@]~ , ($: }.)~) === ({...@] , ($: }.))~
and use > instead of <: (together with interchanging elements of
the first gerund) in order to reduce parenthesizing, and, finally,
use *...@*&# instead of +.&(0 = #)
we get:
a =. {...@] , (merge1 }.)
merge1=: a...@.(>&{.)`,@.(*...@*&#)
10 1 merge 0 1 2 3 4
0 1 2 3 4 10 1
10 1 merge1 0 1 2 3 4
0 1 2 3 4 10 1
1 2 3 merge 2.1 5.1 merge 0 1 2 3 4
0 1 1 2 2 2.1 3 3 4 5.1
1 2 3 merge1 2.1 5.1 merge1 0 1 2 3 4
0 1 1 2 2 2.1 3 3 4 5.1
--
View this message in context:
http://old.nabble.com/Rosetta-code%3A-Merge-Sort-tp27131286s24193p27137381.html
Sent from the J Programming mailing list archive at Nabble.com.
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
