Sorting on Partially Connected Mesh Networks
Xuerong Feng, Chunlei Liu, Jun Kong · 2008
We consider sorting problems based on compare-and- exchange operations on partially connected mesh networks, where n node are organized in sequence and each connects to its k nearest neighbors on both sides. Each node holds a distinct key and these keys need to be sorted in certain order. We present a sequential algorithm with 3/8kn2+ O(nlogn) time complexity and a parallel algorithm with 3/2kn + O(logn) time complexity.