Editing Sorting algorithm (section)

==== Merge sort ====
{{Main|Merge sort}}
''Merge sort'' takes advantage of the ease of merging already sorted lists into a new sorted list. It starts by comparing every two elements (i.e., 1 with 2, then 3 with 4...) and swapping them if the first should come after the second. It then merges each of the resulting lists of two into lists of four, then merges those lists of four, and so on; until at last two lists are merged into the final sorted list.<ref>{{harvnb|Wirth|1986|pp=101–102}}</ref> Of the algorithms described here, this is the first that scales well to very large lists, because its worst-case running time is O(''n'' log ''n''). It is also easily applied to lists, not only arrays, as it only requires sequential access, not random access. However, it has additional O(''n'') space complexity and involves a large number of copies in simple implementations.

Merge sort has seen a relatively recent surge in popularity for practical implementations, due to its use in the sophisticated algorithm [[Timsort]], which is used for the standard sort routine in the programming languages [[Python (programming language)|Python]]<ref>{{cite web|url=http://svn.python.org/projects/python/trunk/Objects/listsort.txt|title=Tim Peters's original description of timsort|website=python.org|access-date=14 April 2018|archive-date=22 January 2018|archive-url=https://web.archive.org/web/20180122024335/http://svn.python.org/projects/python/trunk/Objects/listsort.txt|url-status=live}}</ref> and [[Java (programming language)|Java]] (as of [[JDK7]]<ref>{{cite web|url=http://cr.openjdk.java.net/~martin/webrevs/openjdk7/timsort/raw_files/new/src/share/classes/java/util/TimSort.java|title=OpenJDK's TimSort.java|website=java.net|access-date=14 April 2018|archive-date=14 August 2011|archive-url=https://web.archive.org/web/20110814013719/http://cr.openjdk.java.net/~martin/webrevs/openjdk7/timsort/raw_files/new/src/share/classes/java/util/TimSort.java|url-status=dead}}</ref>). Merge sort itself is the standard routine in [[Perl]],<ref>{{cite web|url=http://perldoc.perl.org/functions/sort.html|title=sort – perldoc.perl.org|website=perldoc.perl.org|access-date=14 April 2018|archive-date=14 April 2018|archive-url=https://web.archive.org/web/20180414233802/http://perldoc.perl.org/functions/sort.html|url-status=live}}</ref> among others, and has been used in Java at least since 2000 in [[Java version history#J2SE 1.3|JDK1.3]].<ref name="mergesort_in_jdk13">[http://java.sun.com/j2se/1.3/docs/api/java/util/Arrays.html#sort(java.lang.Object%5B%5D) Merge sort in Java 1.3], Sun. {{Webarchive|url=https://web.archive.org/web/20090304021927/http://java.sun.com/j2se/1.3/docs/api/java/util/Arrays.html#sort(java.lang.Object%5B%5D) |date=2009-03-04 }}</ref>