Sort race. (9th May 2022)
- Record Type:
- Journal Article
- Title:
- Sort race. (9th May 2022)
- Main Title:
- Sort race
- Authors:
- Zhang, Hantao
Meng, Baoluo
Liang, Yiwen - 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.
- Is Part Of:
- Software, practice & experience. Volume 52:Number 8(2022)
- Journal:
- Software, practice & experience
- Issue:
- Volume 52:Number 8(2022)
- Issue Display:
- Volume 52, Issue 8 (2022)
- Year:
- 2022
- Volume:
- 52
- Issue:
- 8
- Issue Sort Value:
- 2022-0052-0008-0000
- 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 - Journal URLs:
- http://onlinelibrary.wiley.com/ ↗
- DOI:
- 10.1002/spe.3091 ↗
- Languages:
- English
- ISSNs:
- 0038-0644
- Deposit Type:
- Legaldeposit
- View Content:
- Available online (eLD content is only available in our Reading Rooms) ↗
- Physical Locations:
- British Library DSC - 8321.453000
British Library DSC - BLDSS-3PM
British Library STI - ELD Digital store - Ingest File:
- 22404.xml