Notes > Computation and Algorithms > Merge Sort Algorithm

The Merge Sort is a recursive "divide and conquer" algorithm which involves merging two sorted lists with each other each step of the algorithm. As with the insertion sort, a single element is viewed as a sorted list therefore the Merge Sort breaks down a list into individual elements, all of which are "sorted" lists in themselves, which can be merged with other sorted lists.
In the example of an unsorted list of 4 elements, each of the elements will be separated from each other. Then, the first step of the algorithm will merge the first two elements together so that they are in order. Then the 3rd and 4th elements will be merged. This leaves two sorted lists of 2 elements each. These two lists can then be merged, resulting in the 4 elements being sorted in a single list.
The time complexity of the Merge Sort is O(N log(N)). The Merge Sort is a relatively fast algorithm but it has the disadvantage of requiring a large amount of memory due to its recursive nature.
Search for "Merge Sort" on:
Google 
Kelkoo 
Amazon 
eBay (UK) 
eBay (US)
Search for "Merge Sort" on the rest of Computing Students: Merge Sort
