S-ARRAY: Highly Scalable Parallel Sorting Algorithm

The problem of sorting a sequence of N elements on a parallel computer with K processors has been discussed since 1975 when parallel computing came into existence. Presently, with exponential increase in amount of data and computing power, a sorting algorithm is required where all the N available processors are utilized without an increase in overhead of merging. Due to increase in computation power, research of new sorting algorithms has been slowed down. Our proposal S-Array algorithm, is an approach of parallel execution of sort operation based on “Divide and Conquer” principal in a general multiprocessor architecture like NUMA (Non Uniform Multiprocessor Architecture). S-Array is based on master–slave configuration that consists of processors in multiples of four where input is given in form of 22n. S-Array is designed in such a way that even if we increase number of input data and number of processing units, time complexity to sort increased amount of input data remains same i.e. O(log(log(n))/2)+c. Our future work lies in computing performance of S-Array when it sorts huge data in different architectures.