We propose an algorithm for merging two sorted sequences of length k · m stored in two sequences of m stations of single-hop single-channel radio network, where each station stores a block of of k consecutive elements. The time and energetic cost of this algorithm are 6m · k + 8m — 4 and 8k + 4[log_2(m + 1)] +6, respectively. This algorithm can be applied for sorting a sequence of length N = k · n in a network consisting of n stations with memory limited by Θ(k) words. For k = Ω(lg n), the energetic cost of such sorting is O(k · lg n) and the time is O(N lg n). Moreover, the constants hidden by the big "Oh" are reasonably small, to make the algorithm attractive for practical applications.
展开▼
