Algorithms and average time bounds of sorting on a mesh-connected computer

Three new parallel sorting algorithms are developed to enable resolution of the fundamental theoretical problem of sorting. The three algorithms are applied to a mesh connected computer having wrap around connections such as torus. The algorithms have queue size of 1, and can sort n squared random input data. Input data are sorted out into snake type blocked major orders.