Three New Sorting Algorithms Based on a Distribute-Collect Paradigm

• Main Author: P. Y. Padhye
• Other Authors: The Pennsylvania State University CiteSeerX Archives
• Format: Text
• Language: English
• Published: 1993
• Subjects: The Pointers
• Online Access: http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.139

Three new sorting algorithms, called StackSort, DeqSort and MinMaxSort, are described. They are of interest for the following reasons: they are adaptive sorting algorithms; they are comparison based general sorting algorithms; they do not put any restriction on the type of keys; they use linked lists; the moves or exchanges of data required in algorithms using arrays are unnecessary; the desired order is obtained by adjustment of the pointers; they provide examples of interesting applications of data structures such as stacks, queues, and singly- and doubly-linked lists. A new and improved variation of the well known Natural MergeSort, called here SublistMergeSort, is also presented. These algorithms are compared with one another and with other well known sorting algorithms such as InsertionSort and HeapSort in terms of times required to sort various input lists. Input lists of various sizes and degrees of 'presortedness ' were used in the comparison tests. It has been demonstrated that the performance of DeqSort and MinMaxSort is better than InsertionSort and comparable to HeapSort; and that StackSort performance is better than InsertionSort in most cases. 1.