Robust-ShuffleMerge: a stable and in-situ merging algorithm

摘要

The problem of merging sorted lists is a basic computer science problem. Efficient algorithms that tackle the merging sorted lists are significant in various applications which vary from particle simulation to managing the data cluster environments. While the proposed methods handle the balanced length lists, the performance of the decline for the list with unequal lengths; moreover methods which depend on recursive calls face a stack overflow problem. In this paper, we propose Robust-ShuffleMerge to overcome this problem. The merging algorithm is in-situ and stable. The proposed algorithm prunes the input lists in such a way as to convert the inputs into balanced length lists. It is based on the well known ShuffleMerge algorithm. The experiential results show that the proposed algorithm is faster than the original one in merging the unbalanced length lists; and it can merge the lists that the original one fails to merge.