A simple shuffle-based stable in-place merge algorithm

Dalkılıç M. E. , Acar E., Tokatlı G.

1st World Conference on Information Technology (WCIT), İstanbul, Turkey, 6 - 10 October 2010, vol.3 identifier identifier


Sorting is one of the most fundamental problems in computer science. Divide-and-conquer based sorting algorithms use successive merging to combine sorted arrays; therefore performance of merging is critical for these types of applications. The classic merge algorithm uses an extra O(m+n) memory for combining arrays of size m and n. Some improvements on merge algorithms include in-place methods which reduce or eliminate additional memory space, thus getting more practical value.