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 $\frac{3}{8k}n^2$ + $O(n log n)$ time complexity and a parallel algorithm with $\frac{3}{2k}n$ + $O(log n)$ time complexity.