Sorting algorithm
Algorithm that reorders list elements into a specified order.
Last updated
The problem has attracted extensive research since the beginning of computing because of the challenge of solving it efficiently.[1] New sorting algorithms continue to be invented, with Timsort dating to 2002 and the library sort first published in 2006.[1]
Quick Facts
- Definition
- Algorithm that reorders elements into monotonic order as a permutation of the input
- Key requirement
- Output must be in monotonic order and a permutation of the input
- Asymptotically optimal known since
- Mid-20th century
Facts from the source article.
Key facts and history
Bubble sort was analyzed as early as 1956.[1] Asymptotically optimal algorithms have been known since the mid-20th century.[1] Betty Holberton, who contributed to the ENIAC and UNIVAC projects, was one of the people who wrote early sorting algorithms around 1951.[1] Insertion sort processes each element sequentially, placing it into the appropriate spot within a newly formed sorted sequence.[2]
Selection sort locates the smallest element, exchanges it with the element at the first index, then repeats this process on the unsorted portion.[3] Heapsort is a significantly improved variant of selection sort that employs a heap data structure.[3] Quicksort is a divide-and-conquer method that uses a partition step centered on a chosen pivot element.[4] Donald Shell created Shellsort in 1959; it enhances insertion sort by shifting misplaced elements across multiple positions at once.[5]
What the cited sources add
The Perl documentation notes that the sort function in the current version of Perl is implemented via the mergesort algorithm.[6] Perl's sort has been stable since version 5.8.0, meaning elements that compare the same retain their relative order.[6]
References
- Wikipedia, "Sorting algorithm" (CC BY-SA 4.0), which cites: "Meet the 'Refrigerator Ladies' Who Programmed the ENIAC", Mental Floss, 2013-10-13; Lohr, "Frances E. Holberton, 84, Early Computer Programmer", NYTimes, Dec 17, 2001; Demuth, "Electronic Data Sorting", Stanford University, 1956 (we also read that source) en.wikipedia.org
- Wikipedia, "Sorting algorithm" (CC BY-SA 4.0), which cites: Wirth, "Algorithms & Data Structures", Prentice-Hall, 1986, p. 76–77 (we also read that source) en.wikipedia.org
- Wikipedia, "Sorting algorithm" (CC BY-SA 4.0) en.wikipedia.org
- Wikipedia, "Sorting algorithm" (CC BY-SA 4.0), which cites: ; Cormen, "Introduction to Algorithms", The MIT Press, 2009, p. 171–172 (original not read by us) en.wikipedia.org
- Wikipedia, "Sorting algorithm" (CC BY-SA 4.0), which cites: Shell, "A High-Speed Sorting Procedure", Communications of the ACM, 1959, p. 30–32 (original not read by us) en.wikipedia.org
- "sort – perldoc.perl.org", perldoc.perl.org. facts only, no text reused. perldoc.perl.org
Each numbered sentence above was checked against the source it cites before publication. Sentences citing Wikipedia adapt text from the English Wikipedia article Sorting algorithm (contributors), used under CC BY-SA 4.0; this entry is available under the same licence. Other sources were used for facts only; no text or images are copied from them.
More in Complexity Theory
Sources
Compiled from Wikipedia and the sources listed below. Text from Wikipedia is available under CC BY-SA 4.0; this entry is adapted from it.
- Wikipedia: Sorting algorithm (CC BY-SA 4.0).
Spotted an error? Know more?
Reader corrections go straight into our review queue. Suggest an edit · How this site is sourced