AN ALGORITHM HELPS REDUCE THE NUMBER OF COMPARISONS FOR SORTING X + Y

Abstract

This paper proposes an efficient algorithm for comparison reduction for sorting X + Y. The proposed algorithm first sorts set X and set Y individually, then repeatedly selects a pair of elements from X and Y and adds the pair into X + Y in ascending order of sums of pairs. The algorithm is designed with a technique able to limit the number of pairs to be considered for each selection. The technique is able to limit the number of elements of X to be considered and considers only one element of Y to be paired with each element of X to select the pair with the smallest sum among the pairs that haven’t been selected. A heap data structure used to store and update pairs to be considered helps operations in selecting a pair only need to run in O(log(n)) time, and the total running time of the algorithm is O(n²log(n)). The experimental results show that the number of comparisons and the running time of the proposed algorithm are significantly less than those of a traditional heapsort based approach.