I am currently researching the best algorithms available to achieve an inplace merge operation: consider two consecutive sorted arrays of size
m, and the goal is to merge it in place into a single sorted array (of size
n + m).
I have found this reference (Geffet et al., 2000), but I was wondering if better algorithms were found since then.
I am interested in research in three categories about these algorithms:
- stable inplace merge (regardless of the "implementation difficulty" of the algorithm)
- unstable inplace merge (regardless of the "implementation difficulty" of the algorithm)
- "easily implementable" stable inplace merge
What are the current bests algorithms in these categories?