Title :
Sorting on Partially Connected Mesh Networks
Author :
Feng, Xuerong ; Liu, Chunlei ; Kong, Jun
Author_Institution :
Valdosta State Univ., Valdosta
Abstract :
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.
Keywords :
communication complexity; computer networks; sorting; compare-and- exchange operations; k nearest neighbors; parallel algorithm; partially connected mesh networks; sequential algorithm; sorting problems; time complexity; Bioinformatics; Computer science; Information technology; Mesh generation; Mesh networks; Nearest neighbor searches; Neodymium; Parallel algorithms; Sorting; Upper bound; Mesh network; Parallel processing; Sorting algorithm; Sorting network;
Conference_Titel :
Information Technology: New Generations, 2008. ITNG 2008. Fifth International Conference on
Conference_Location :
Las Vegas, NV
Print_ISBN :
0-7695-3099-0
DOI :
10.1109/ITNG.2008.215
