Sort race. (9th May 2022)

• Record Type: Journal Article
• Authors: Zhang, Hantao; Meng, Baoluo; Liang, Yiwen
• Is Part Of: Software, practice & experience. Volume 52:Number 8(2022)
• Page Start: 1867
• Page End: 1878
• Publication Date: 2022-05-09
• Subjects: merge sort -- quick sort -- sorting algorithms; Computer software -- Periodicals; Computer programming -- Periodicals; Computer programs -- Periodicals; 005.3
• DOI: 10.1002/spe.3091
• Languages: English
• ISSNs: 0038-0644

Abstract

Abstract: Sorting is one of the oldest computing problems and is still very important in the age of big data. Numerous algorithms and implementation techniques have been proposed. In this study, we focus on comparison based, internal sorting algorithms. We created 12 types of data of various sizes for experiments and tested extensively various implementations in a single setting. Using some effective techniques, we found that quicksort is adaptive to nearly sorted inputs and is still the best overall sorting algorithm. We also identified techniques that are effective in timsort, which is one of the most popular and efficient sorting methods based on natural mergesort . In addition, we created a version of our own mergesort, which performs better than timsort on nearly sorted instances. Our implementations of quicksort and mergesort are different from other implementations reported in all textbooks or research articles, and are faster than any version of the C library qsort functions not only for randomly generated data, but also for various types of nearly sorted data. This work can aid the user to choose the best sorting algorithm for the hard sorting job at hand, and provides a platform for anyone to test their own sorting algorithm against the best in the field.