Merge Sort - Pseudocode

Merge Sort

Merge sort is a recursive algorithm that continually splits a list in half until each half is either empty or one item, at which point the two halves are merged together in natural order, back up the division process until the entire list has been sorted.

Merge Sort Pseudocode

void mergeSort( pass-by-reference int [] list) //method for initial call
  int n ← list.length  int[] temp ← new int[n] //creates a temporary 

utility array
  mergeSortHelper(list, 0, n - 1, temp)
end mergeSort
void mergeSortHelper ( pass-by-reference int[] list, int front, 
                       int back, pass-by-reference int[] temp )
  if (front < back) //if front and back are not equal and have not 

crossed    int mid ← (front + back)/2 //find the middle position
    mergeSortHelper(list, front, mid, temp) //sort the left side
    mergeSortHelper(list, mid + 1, back, temp) //sort the right side
    merge(list, front, mid, back, temp) //merge the two sides
  end if 
end mergeSortHelper    
void merge ( pass-by-reference int_array list, int front, int mid
             int back, pass-by-reference int_array temp)
  int i ← front //i marks the front of the left side list being merged
  int j ← mid + 1 //j marks the front of the right side list being merged  int k ← front //k marks the front of the temporary list that receives                 //the two merged sides
  while (i <= mid && j <= back) //while both sides still contain values
    if (list[i] < list[j]) //if the left front value is less than 
                           //the right front value
      temp[k] ← list[i] //put left front value into the temp list      

i ← i + 1 //and move up one value on the left side    else //otherwise
      temp[k] ← list[j] //put right side front value into temp list      

j ← j + 1 //and move up one value on the right side    end if else
    k ← k + 1
  end while

//At this point, one of the two halves of the list has been completely loaded into the
temporary array. If the left half still has values, this is the code to clean out the
remaining left half into the temporary list.
  while (i <= mid)
   temp[k] ← list[i] //put i's value into temporary list
   k ← k + 1 //step both k and i one place to the right
   i ← i + 1
  end while
//If the right half still has values, this is the code to clean out the remaining
right half into the temporary list
  while (j <= back)
   temp[k] ← list[j] //put j's value into temporary list   j ← j + 1 //step both k and j one place to the right   k ← k + 1  end while
//This is the final step: load all values in the temporary list back into the
original list
  for (int x ← front; x <= back; x ← x + 1)
   list[x] ← temp[x]
  end forend merge

Best, Average, and Worst Case for a Merge Sort

This O(N log N) process uses a "divide and conquer" process to continuously divide a list into smaller and smaller halves until each half is just one item, then reassembles, or "merges" the two smaller halves into a sorted "larger" half, repeating this divide and merge process until the entire list has been merged into one sorted list.  The efficiency of this sort is offset to a degree by the memory cost required, double the size of the list, since part of its process is the use of a temporary array the same size as the original array.