So, a few things.
First, to patch the code, as you suggest, I tried
o =. (+i.@#)@:I.
u =. i.@+&#
oo =. o,~u-.o
merge =. ,`oo`,}
I have split the whole merge function to be readable. Essentially, I
applied your idea that the indexes for the other array should be the
indexes that are not of the first one. It works for in all cases, in O(n
log(n)) if -. takes O(n), which is what is disclosed in the i. family
wiki page.
However, the whole idea has a big flaw, IMO. It's that merge is in O(n
log(n)). This might sound acceptable (in the end, it just means that
mergesort implemented this way will be in O(n log²(n))) However, when
you think about it, it's the same complexity than simply sorting x,y, so
in fact you don't really take advantage of the fact that the two arrays
are already sorted (I mean, you do, because otherwise it would not work,
but your complexity is not better than if they were not).
This does not mean it could not work, but it's not completely satisfactory.
Adrien Mathieu
On 05/10/2021 20:37, Adrien Mathieu wrote:
Thank you for this reply, this is pretty much what I was looking for.
I'll probably still have questions, but I need to assimilate this code
first (so small and yet so information-heavy).
Adrien Mathieu
On 05/10/2021 19:56, Marshall Lochbaum wrote:
While I don't think arrays will ever be as elegant for merge sort as
quicksort, I did recently find a strategy for merging sorted arrays
using binary searches. Here's a version that works if the two sides
don't share any elements:
o =. (+i.@#)@:I.
'addfhk' ,`(o~,o)`,} 'bcceg'
abccddefghk
To fix it for arbitrary sorted arguments, the I. in o (but not o~) needs
to be changed to place elements of y after equal elements of x, making
('ace'I.'bc') evaluate to 1 2 instead of 1 1 for example.
The idea is to find the intended position of each element, then place
them there with amend. Here's an expansion of the rather obscure
gerund-amend pattern:
x ,`(o~,o)`,} y
(x,y) (x(o~,o)y)} x,y NB. same as above
The right side is just a container to put results in. It needs to have
the right size but its elements will all be overwritten. The left side
is the elements to insert, and the middle is the indices, the important
part of the algorithm.
Here's how the indices work: The final position of an entry is the
number of entries that will come before it. That's the number of smaller
entries plus the number of equal entries with smaller indices. When
merging x,y, x and y are both sorted, so we can simplify: for an element
of x, it's the number of strictly smaller entries in y plus the number
of previous entries in x.
Continuing just with x, the number of previous entries for each element
is (i.#x). Element 0 is preceeded by 0 other elements, 1 by 1 other
element, and so on. The number of smaller entries in y is found by
(y I. x). In fact I usually take this as the definition of I. . So
((i.#x) + y I. x), or (y (+i.@#)@:I. x), gives the number of entries
that will come before a given element of y, or its final position. This
is o~ in the complete solution.
The same analysis almost works for y. The position of an element of y is
the number of previous elements of y plus the number of smaller or equal
elements of x. It's the "or equal" that makes the difference, and that's
why a modified version of I. would need to be used.
There are many related solutions as well, and probably some that would
be simpler. It's worth noting that only one side of (o~,o) needs to be
known to merge the two arrays, as the other side just contains all the
missing indices in order.
Marshall
On Tue, Oct 05, 2021 at 06:03:15PM +0200, Adrien Mathieu wrote:
Hello,
I am a beginner, and I would like to know if there is a way to write
mergesort without using loops, or an ugly translation of loops using
the ^:
conjunction.
In particular, I have the impression that the merge part is hard to
achieve.
Thanks in advance,
Adrien Mathieu
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
----------------------------------------------------------------------
For information about J forums see http://www.jsoftware.com/forums.htm
