Computing Students - Computer Science Degree Notes
Home Contact Shop Notes Questions Programming Links Dictionary Coursework FORUM Tutors
  Recommended Amazon Searches: Computer Science | Computing | Computer Systems | Database | Computing Revision  

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

Home | Contact | Shop | Notes | Questions | Programming | Links | Dictionary | Coursework | Tutors Sponsored Links: Affiliate Program Articles | Computer Science Definitions | CS Degree Notes
Copyright © 2005-2009
This site is to be used in accordance with the User Agreement
High Wycombe Web Design