Merge Sort





Definition: A process designed to sort an unordered set of linear data into either ascending order (lowest to highest) or descending order (highest to lowest). This is done by repeatedly breaking the dataset in half until every single element is isolated and then reassembling it while sorting elements along the way. See below for an example.


Procedure for ASCENDING Merge Sort:

  1. Repeatedly divide the dataset in half until every element is isolated.

    2. Note: If a dataset has an odd number of elements, it can be split into two lists of sizes differing by 1. For example, a list with 3 elements can be split into two lists, one of size 1 and one of size 2. In the next step, the size 2 list would be split into two different size 1 lists.

  2. The structure is reassembled. Each time that elements are merged, they are sorted into ascending order.

Fun Fact: Merge sort is a very consistent sorting algorithm. It is known to perform well regardless of how out of place the initial elements may be.



Commonly Used In: