Merge sort is a recursive algorithm for sorting lists.
Algorithm Edit
This algorithm uses two assumptions
 It is easier to sort two smaller sorted lists than one big list
 lists of one item are already considered sorted
The list is recursively split at a pivot point (by convention the middle node in the list). Once you hit a single item that item can be returned. When joining larger lists, repeatedly compare the two items at the start of each list and add the smaller item onto the result list until one of the lists runs out. Then the remaining list can be added onto the end of the result list.
Pseudocode Edit
merge_sort(arr) initialize list left, right if arr.count ≤ 1 return arr middle = arr.count / 2 // integer division for each x in arr up to middle add x to left for each x in arr after middle add x to right left = merge_sort(left) right = merge_sort(right) result = merge(left, right) return result merge(left, right) initialize list result while left.count > 0 and right.count > 0 if left at 0 ≤ right at 0 result.add(left at 0) left.remove at 0 else result.add(right at 0) right.remove at 0 if left.count > 0 result.addlist(left) if right.count > 0 result.addlist(right) return result
Trivia Edit
 Merge Sort is the sort algorithm used for the sort method in
java.util.Collections
andjava.util.Arrays
.
See Also Edit
