# Adaptive sort

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Adaptive_sort
> Markdown URL: https://mediated.wiki/source/Adaptive_sort.md
> Source: https://en.wikipedia.org/wiki/Adaptive_sort
> Source revision: 1302868249
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{Short description|Sorting algorithms which exploit existing order in its input}}
A [sorting algorithm](/source/sorting_algorithm) falls into the '''adaptive sort''' family if it takes advantage of existing order in its input.  It benefits from the presortedness in the input sequence – or a limited amount of [disorder](/source/randomness) for various definitions of measures of disorder – and sorts faster.  Adaptive sorting is usually performed by modifying existing sorting algorithms.

== Motivation ==
[Comparison-based sorting algorithms](/source/Comparison_sort) have traditionally dealt with achieving an optimal bound of ''[O](/source/Big_O_notation)''(''n'' log ''n'') when dealing with [time complexity](/source/time_complexity).  Adaptive sort takes advantage of the existing order of the input to try to achieve better times, so that the time taken by the algorithm to sort is a smoothly growing function of the size of the sequence ''and'' the disorder in the sequence.  In other words, the more presorted the input is, the faster it should be sorted.

This is an attractive feature for a sorting algorithm because sequences that nearly sorted are common in practice.  Thus, the performance of existing sorting algorithms can be improved by taking into account the existing order in the input.

Most worst-case sorting algorithms that do optimally well in the worst-case, notably [heap sort](/source/heap_sort) and [merge sort](/source/merge_sort), do not take existing order within their input into account, although this deficiency is easily rectified in the case of [merge sort](/source/merge_sort) by checking if the last element of the left-hand group is less than (or equal) to the first element of the righthand group, in which case a merge operation may be replaced by simple concatenation – a modification that is well within the scope of making an algorithm adaptive.

== Examples ==
A classic example of an adaptive sorting algorithm is [insertion sort](/source/insertion_sort).<ref name="Estivill"/>  In this sorting algorithm, the input is scanned from left to right, repeatedly finding the position of the current item, and inserting it into an array of previously sorted items.

[Pseudo-code](/source/Pseudo-code) for the insertion sort algorithm follows (array X is [zero-based](/source/Zero-based_numbering)):

 '''procedure''' Insertion Sort (X):
     '''for''' j = 1 '''to''' length(X) - 1 '''do'''
         t ← X[j]
         i ← j
         '''while''' i > 0 '''and''' X[i - 1] > t '''do'''
             X[i] ← X[i - 1]
             i ← i - 1
         '''end'''
         X[i] ← t
     '''end'''

The performance of this algorithm can be described in terms of the number of [inversions](/source/Inversion_(discrete_mathematics)) in the input, and then {{tmath|T(n)}} will be roughly equal to {{tmath|I(A) + (n - 1)}}, where {{tmath|I(A)}} is the number of inversions.  Using this measure of presortedness – being relative to the number of inversions – insertion sort takes less time to sort the closer the array of data is to being sorted.

Other examples of adaptive sorting algorithms are [adaptive heap sort](/source/adaptive_heap_sort), [adaptive merge sort](/source/Merge_sort), [patience sort](/source/patience_sort),<ref name="Chandramouli">{{Cite conference |last1=Chandramouli |first1=Badrish |last2=Goldstein |first2=Jonathan |title=Patience is a Virtue: Revisiting Merge and Sort on Modern Processors |conference=SIGMOD/PODS |year=2014|url=https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/patsort-sigmod14.pdf}}</ref> [Shellsort](/source/Shellsort), [smoothsort](/source/smoothsort), [splaysort](/source/splaysort), [Timsort](/source/Timsort), and [Cartesian tree sorting](/source/Cartesian_tree).<ref>{{cite conference
 | last1 = Levcopoulos | first1 = Christos
 | last2 = Petersson | first2 = Ola
 | contribution = Heapsort - Adapted for Presorted Files
 | doi = 10.1007/3-540-51542-9_41
 | location = London, UK
 | pages = 499–509
 | publisher = Springer-Verlag
 | series = Lecture Notes in Computer Science
 | title = WADS '89: Proceedings of the Workshop on Algorithms and Data Structures
 | volume = 382
 | year = 1989| isbn = 978-3-540-51542-5
 }}</ref>

== See also ==
* [Sorting algorithms](/source/Sorting_algorithms)

== References ==
* {{cite book
  | last = Hagerup
  | first = Torben
  |author2= Jyrki Katjainen
  | title = Algorithm Theory – SWAT 2004
  | publisher = Springer-Verlag
  | year = 2004
  | location = Berlin Heidelberg
  | pages = 221–222
  | url = https://books.google.com/books?id=2E-KNhKl3gEC&q=adaptive+sort&pg=PA221
  | isbn = 3-540-22339-8}}
* {{cite book
  | last = Mehta
  | first = Dinesh P.
  |author2= Sartaj Sahni
  |author2-link= Sartaj Sahni
  | title = Data Structures and Applications
  | publisher = Chapman & Hall/CRC
  | year = 2005
  | location = USA
  | pages = 11‑8–11‑9
  | url = https://books.google.com/books?id=fQVZy1zcpJkC&q=adaptive+sort&pg=PT230
  | isbn = 1-58488-435-5}}
* {{cite book
  | last = Petersson
  | first = Ola
  |author2= Alistair Moffat
  | title = A framework for adaptive sorting
  | volume = 621
  | pages = 422–433
  | publisher = Springer Berlin / Heidelberg
  | location = Berlin
  | year = 1992
  | issn = 1611-3349
  | doi = 10.1007/3-540-55706-7_38
  | series = Lecture Notes in Computer Science
  | isbn = 978-3-540-55706-7
  }}

{{Reflist|refs=
<ref name="Estivill">
{{cite journal
  | doi = 10.1145/146370.146381
  | last1 = Estivill-Castro
  | first1 = Vladmir
  |first2= Derick |last2=Wood | title = A survey of adaptive sorting algorithms
 | journal = ACM Computing Surveys
 | author2-link = Derick Wood
  | volume = 24
  | issue = 4
  | pages = 441–476
  | location = New York, NY, USA
  | date = December 1992
  | citeseerx = 10.1.1.45.8017
  | s2cid = 1540978
 | issn = 0360-0300}}
</ref>}}

{{sorting}}

Category:Sorting algorithms

---
Adapted from the Wikipedia article [Adaptive sort](https://en.wikipedia.org/wiki/Adaptive_sort) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Adaptive_sort?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.