TY - JFULL
AU - Hanan Ahmed-Hosni Mahmoud and Nadia Al-Ghreimil
PY - 2008/11/
TI - A Novel In-Place Sorting Algorithm with O(n log z) Comparisons and O(n log z) Moves
T2 - International Journal of Computer and Information Engineering
SP - 3483
EP - 3489
VL - 2
SN - 1307-6892
UR - https://publications.waset.org/pdf/10106
PU - World Academy of Science, Engineering and Technology
NX - Open Science Index 22, 2008
N2 - 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.
ER -