FANDOM


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

 See Also Edit

Sorting algorithms
Bubble sort - Insertion sort - Merge sort - Quicksort - Selection sort - Heap sort

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.