Editing Sorting algorithm (section)

==== Heapsort ====
{{Main|Heapsort}}
''Heapsort'' is a much more efficient version of [[selection sort]]. It also works by determining the largest (or smallest) element of the list, placing that at the end (or beginning) of the list, then continuing with the rest of the list, but accomplishes this task efficiently by using a data structure called a [[heap (data structure)|heap]], a special type of [[binary tree]].<ref>{{harvnb|Wirth|1986|pp=87–89}}</ref> Once the data list has been made into a heap, the root node is guaranteed to be the largest (or smallest) element. When it is removed and placed at the end of the list, the heap is rearranged so the largest element remaining moves to the root. Using the heap, finding the next largest element takes O(log ''n'') time, instead of O(''n'') for a linear scan as in simple selection sort. This allows Heapsort to run in O(''n'' log ''n'') time, and this is also the worst-case complexity.