4 ms·
It looks like this is not really an “in-place” algorithm as it uses O(n) temporary space for the array of references. (If you allow that, one can always make a
by anderskaseorg 5y ago
It looks like this is not really an “in-place” algorithm as it uses O(n) temporary space for the array of references. (If you allow that, one can always make an array of references, use any algorithm to perform a merge on the references, then use the references to permute the original array.)
There are in-place algorithms for merging, such as Bing-Chao Huang, Michael A. Langston, “Practical In-Place Merging” (1988): http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.88.1155 http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.88.1...
- klysm 5y agoYeah I guess the data itself is remaining in place, maybe there’s better name for this? Copy free perhaps?
- HWR_14 5y agoWould o(n+m) really be a record? I didn't see any claims on your paper about computation cost, but I have only had time to read it's summary.
- Someone 5y agoIf, in a row of n+m items, you have to move the first one to the end and all other ones one place forward, you can, at best, move one item to its correct place per swap, except for the last swap. So, worst case, you can’t do with fewer than n+m-1 swaps. In general, to perform a permutation, you can put each of its cycles in the correct spot with one fewer swap than the number of items in the cycle. So, for a permutation with k cycles, the best you can do is n+m-k swaps.