Merge algorithm: Difference between revisions

Revision as of 02:09, 27 June 2019

Revision as of 02:09, 27 June 2019

Line 6:

The merge algorithm plays a critical role in the [[merge sort]] algorithm, a [[comparison sort|comparison-based sorting algorithm]]. Conceptually, 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. A list containing a single element is, by definition, sorted, 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.