Generally speaking, when sorting performance is actually the issue, we use J's sorting primitive.
Implementations of sorting using other techniques are primarily beneficial for modelling and educational purposes. And, yes, you are correct that that's not completely satisfactory. But in many cases it's the right approach. Take care, -- Raul On Wed, Oct 6, 2021 at 1:17 PM Adrien Mathieu <[email protected]> wrote: > > 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 ---------------------------------------------------------------------- For information about J forums see http://www.jsoftware.com/forums.htm
