Adaptive sorting techniques for nearly reverse sorted lists

• Main Author: Go, Nonoy A.
• Format: text
• Language: English
• Published: Animo Repository 2008
• Subjects: Computer algorithms; Sorting (Electronic computers); List processing (Electronic computers)
• Online Access: https://animorepository.dlsu.edu.ph/etd_masteral/3728
• Institution: De La Salle University

There are many sorting algorithms, which are adaptive on different types of disorder measurements. Existing adaptive algorithms, which uses Runs as a division protocol, performs well on low runs percentages. However, the adaptiveness reduces whenever the given list is in a nearly reverse sorted manner; in short, lists of high run percentages. Although Enc-adaptive sorting algorithms like Melsort solves this problem, it runs at O(n2); which puts its practicality in question. In this paper, we present possible modifications of natural mergesort by incorporating techniques like utilization of Reverse Runs and Loose Enc rules as division protocols. Both methods have shown to be O(nlogn) and tend to have less comparisons against existing Run-adaptive sorting algorithms on Run percentages of 70% or higher for array sizes ranging from 50 to 50,000. Keywords: Algorithms, Theory