Open Science Research Excellence
@article{(International Science Index):http://waset.org/publications/10106,
  title    = {A Novel In-Place Sorting Algorithm with O(n log z) Comparisons and O(n log z) Moves},
  author    = {Hanan Ahmed-Hosni Mahmoud and  Nadia Al-Ghreimil},
  country   = {},
  institution={},
  abstract  = {In-place sorting algorithms play an important role in many fields such as very large database systems, data warehouses, data mining, etc. Such algorithms maximize the size of data that can be processed in main memory without input/output operations. In this paper, a novel in-place sorting algorithm is presented. The algorithm comprises two phases; rearranging the input unsorted array in place, resulting segments that are ordered relative to each other but whose elements are yet to be sorted. The first phase requires linear time, while, in the second phase, elements of each segment are sorted inplace in the order of z log (z), where z is the size of the segment, and O(1) auxiliary storage. The algorithm performs, in the worst case, for an array of size n, an O(n log z) element comparisons and O(n log z) element moves. Further, no auxiliary arithmetic operations with indices are required. Besides these theoretical achievements of this algorithm, it is of practical interest, because of its simplicity. Experimental results also show that it outperforms other in-place sorting algorithms. Finally, the analysis of time and space complexity, and required number of moves are presented, along with the auxiliary storage requirements of the proposed algorithm.
},
    journal   = {International Journal of Computer, Electrical, Automation, Control and Information Engineering},  volume    = {2},
  number    = {10},
  year      = {2008},
  pages     = {3484 - 3489},
  ee        = {http://waset.org/publications/10106},
  url       = {http://waset.org/Publications?p=22},
  bibsource = {http://waset.org/Publications},
  issn      = {eISSN:1307-6892},
  publisher = {World Academy of Science, Engineering and Technology},
  index     = {International Science Index 22, 2008},
}