Matrix Sort - A Parallelizable Sorting Algorithm

S. Kavitha; Vijay V.; Saketh A. B.

Research Article

Matrix Sort - A Parallelizable Sorting Algorithm

by S. Kavitha, Vijay V., Saketh A. B.

International Journal of Computer Applications

Foundation of Computer Science (FCS), NY, USA

Volume 143 - Issue 9

Published: Jun 2016

Authors: S. Kavitha, Vijay V., Saketh A. B.

10.5120/ijca2016910341

PDF

S. Kavitha, Vijay V., Saketh A. B. . Matrix Sort - A Parallelizable Sorting Algorithm. International Journal of Computer Applications. 143, 9 (Jun 2016), 1-6. DOI=10.5120/ijca2016910341

                        @article{ 10.5120/ijca2016910341,
                        author  = { S. Kavitha,Vijay V.,Saketh A. B. },
                        title   = { Matrix Sort - A Parallelizable Sorting Algorithm },
                        journal = { International Journal of Computer Applications },
                        year    = { 2016 },
                        volume  = { 143 },
                        number  = { 9 },
                        pages   = { 1-6 },
                        doi     = { 10.5120/ijca2016910341 },
                        publisher = { Foundation of Computer Science (FCS), NY, USA }
                        }

                        %0 Journal Article
                        %D 2016
                        %A S. Kavitha
                        %A Vijay V.
                        %A Saketh A. B.
                        %T Matrix Sort - A Parallelizable Sorting Algorithm%T 
                        %J International Journal of Computer Applications
                        %V 143
                        %N 9
                        %P 1-6
                        %R 10.5120/ijca2016910341
                        %I Foundation of Computer Science (FCS), NY, USA

Abstract

Sorting algorithms are the class of algorithms that result in the ordered arrangement of a list of given elements. The arrangement can be in ascending or descending order based on the requirement given. Time complexity, space complexity and optimality are used to assess the algorithms. In this paper, a new sorting algorithm called Matrix sort is introduced. This algorithm aims to sort the elements of a matrix without dis- pturbing the matrix structure. It has a time complexity of O(n√nlog√n) and hence takes lesser time than existing O(n2) algorithms. A pseudocode for the algorithm is provided and the best, average and worst case time complexities are derived.

References

Donald Knuth. The art of Computer Programming, Volume-3: Sorting and Searching, Third edition. Addison-Wesley, Reading, Massachusetts, 1993.
Hoare, C.A.R.(1961). Algorithm 63,Partition; Algorithm 64,Quicksort; Communications of the ACM, Vol.4, p.321
Robert Sedgewick, Kevin Wayne. Algorithms (4th ed). Annalen der Physik, 322(10):891-921, 1905.
Comparison of algorithms. https://en.wikipedia.org/wiki/Sorting_algorithm
Anany Levitin. Introduction to the Design & Analysis of Algorithms, 2nd Edition.
Mark Allen Weiss. Data Structures and Algorithm Analysis in C++(Third edition). Addison-Welsey (2007)
Robert Sedgewick(1978). Implementing Quicksort programs. Communications of the ACM 21
Daniel H. Greene, Donald E. Knuth. Mathematics for the analysis of algorithms. Modern Birkhüser Classics (2007)
Robert Sedgewick (1998). Algorithms in C: Fundamentals, Data Structures, Sorting, Searching, Parts 1-4 (3rd ed.). Pearson Education
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C.Stein (2009). Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill.
N. G. de Bruijn(1958). Asymptotic Methods in Analysis. Amsterdam: North-Holland. pp. 5â?A ¸ S7.
Papadimitriou, Christos H.(1994). Computational complexity. Reading, Mass.: Addison-Wesley.

Index Terms

Computer Science

Information Sciences

No index terms available.

Keywords

Matrix sort Top-down Parallelizable sorting