Editing Sorting algorithm (section)

== History and concepts ==
From the beginning of computing, the sorting problem has attracted a great deal of research, perhaps due to the complexity of solving it efficiently despite its simple, familiar statement. Among the authors of early sorting algorithms around 1951 was [[Betty Holberton]], who worked on [[ENIAC]] and [[UNIVAC]].<ref name="refrigerator">{{Cite web|url=http://mentalfloss.com/article/53160/meet-refrigerator-ladies-who-programmed-eniac|title=Meet the 'Refrigerator Ladies' Who Programmed the ENIAC|website=Mental Floss|access-date=2016-06-16|date=2013-10-13|archive-date=2018-10-08|archive-url=https://web.archive.org/web/20181008094658/http://mentalfloss.com/article/53160/meet-refrigerator-ladies-who-programmed-eniac|url-status=live}}</ref><ref name="NYTimes">{{cite news|last1=Lohr|first1=Steve|title=Frances E. Holberton, 84, Early Computer Programmer|url=https://www.nytimes.com/2001/12/17/business/frances-e-holberton-84-early-computer-programmer.html|access-date=16 December 2014|publisher=NYTimes|date=Dec 17, 2001|archive-date=16 December 2014|archive-url=https://web.archive.org/web/20141216015437/http://www.nytimes.com/2001/12/17/business/frances-e-holberton-84-early-computer-programmer.html|url-status=live}}</ref> [[Bubble sort]] was analyzed as early as 1956.<ref>{{cite thesis |last=Demuth |first=Howard B. |title=Electronic Data Sorting |type=PhD thesis |publisher=Stanford University |year=1956 |id={{ProQuest|301940891}} }}</ref> Asymptotically optimal algorithms have been known since the mid-20th century{{snd}} new algorithms are still being invented, with the widely used [[Timsort]] dating to 2002, and the [[library sort]] being first published in 2006.

Comparison sorting algorithms have a fundamental requirement of [[Big omega notation|Ω(''n'' log ''n'')]] comparisons (some input sequences will require a multiple of ''n'' log ''n'' comparisons, where n is the number of elements in the array to be sorted). Algorithms not based on comparisons, such as [[counting sort]], can have better performance.

Sorting algorithms are prevalent in introductory [[computer science]] classes, where the abundance of algorithms for the problem provides a gentle introduction to a variety of core algorithm concepts, such as [[big O notation]], [[divide-and-conquer algorithm]]s, [[data structure]]s such as [[heap (data structure)|heap]]s and [[binary tree]]s, [[randomized algorithm]]s, [[best, worst and average case]] analysis, [[time–space tradeoff]]s, and [[upper and lower bounds]].

Sorting small arrays optimally (in the fewest comparisons and swaps) or fast (i.e. taking into account machine-specific details) is still an open research problem, with solutions only known for very small arrays (<20 elements). Similarly optimal (by various definitions) sorting on a parallel machine is an open research topic.