Merge Sort

Merge sort is a divide and conquer algorithm that works by dividing a list continuously and then merging/sorting the smaller lists.

Average and Worst case running time: O(n logn)
n, because you visit all the elements to merge them. log n, because you're constantly split the array in 2, so n/2

Note: It is faster than quick sort because it has a lower constant.

Most implementations of quick sort require O(n) space. That's why some people prefer heap sort which is also O(nlogn) running time, but requires only constant space (O(1)).

An interesting note: Java uses a modified version of merge sort for their sort() algorithm

Implementation of merge sort that you can run:

import java.util.List;
import java.util.ArrayList;

class MergeSort {

   List <Integer> list;
  
   MergeSort() {
       list = new ArrayList<Integer>(6);
       System.out.println("size before we put anything in it: "+list.size());
       list.add(new Integer(1));
       list.add(new Integer(5));
       list.add(new Integer(3));
       list.add(new Integer(4));
       list.add(new Integer(20));
       list.add(new Integer(0));
       list.add(new Integer(6));
       list.add(new Integer(10));
   }

   public static void main (String args[]) {
       MergeSort ms = new MergeSort();
       ms.sort();
   }

   void sort() {
       if (list != null) {
           List<Integer> result = mergesorthelp(list);
          
           for (Integer i: result) {
               System.out.println(i);
           }
       }
   }
  
   List<Integer> mergesorthelp(List<Integer> list){

       if(list.isEmpty() || list.size() == 1) {
           return list;
       }
      
       List<Integer> a, b, result;

       a = mergesorthelp(list.subList(0, (list.size()/2)));
       b = mergesorthelp(list.subList((list.size()/2), list.size()));
      
       result = merge(a, b);
      
       return result;
   }
  
   List<Integer> merge (List<Integer> a, List<Integer> b) { 
       List<Integer> newList = new ArrayList<Integer>();
       int indexA = 0;
       int indexB = 0;
       int sizeA = a.size();
       int sizeB = b.size();
      
       while (indexA < sizeA || indexB < sizeB) {
           if (indexA < sizeA && indexB < sizeB) {
               if (a.get(indexA) > b.get(indexB)) {
                   newList.add(b.get(indexB));
                   indexB++;
               }
               else {
                   newList.add(a.get(indexA));
                   indexA++;
               }
           }
           else if (indexA < sizeA) {
               newList.add(a.get(indexA));
               indexA++;
           }
           else if (indexB < sizeB) {
               newList.add(b.get(indexB));
               indexB++;
           }
       }//end while
      
       return  newList;
   }
}