Editing Merge algorithm (section)

== Application ==
[[File:Merge sort algorithm diagram.svg|thumb|upright=1.5|A graph exemplifying merge sort. Two red arrows starting from the same node indicate a split, while two green arrows ending at the same node correspond to an execution of the merge algorithm.]]
The merge algorithm plays a critical role in the [[merge sort]] algorithm, a [[comparison sort|comparison-based sorting algorithm]]. Conceptually, the merge sort algorithm consists of two steps:

# [[Recursion (computer science)|Recursively]] divide the list into sublists of (roughly) equal length, until each sublist contains only one element, or in the case of iterative (bottom up) merge sort, consider a list of ''n'' elements as ''n'' sub-lists of size 1. A list containing a single element is, by definition, sorted.
# Repeatedly merge sublists to create a new sorted sublist until the single list contains all elements. The single list is the sorted list.

The merge algorithm is used repeatedly in the merge sort algorithm.

An example merge sort is given in the illustration. It starts with an unsorted array of 7 integers. The array is divided into 7 partitions; each partition contains 1 element and is sorted. The sorted partitions are then merged to produce larger, sorted, partitions, until 1 partition, the sorted array, is left.