|
Various sorting algorithms using parallel architectures have been proposed in the search for more efficient results. This paper introduces the Multi-Sort Algorithm for Multi-Mesh of Trees (MMT) Architecture for N = n 4 elements with more efficient time complexity compared to previous architectures. The shear sort algorithm on Single Instruction Multiple Data (SIMD) mesh model requires $4\sqrt{N}+O\sqrt{N}$ time for sorting N elements, arranged on a $\sqrt{N}\times \sqrt{N}$ mesh, whereas Multi-Sort algorithm on the SIMD Multi-Mesh (MM) Architecture takes O ( N 1/4) time for sorting the same N elements, which proves that Multi-Sort is a better sorting approach. We have improved the time complexity of intrablock Sort. The Communication time complexity for 2D Sort in MM is O ( n ), whereas this time in MMT is O (log n ). The time complexity of compare–exchange step in MMT is same as that in MM, i.e., O ( n ). It has been found that the time complexity of the Multi-Sort on MMT has been improved as on Multi-Mesh architecture.
|
