Here is a Java implementation of merge sort. This algorithms runs in O(n*log(n)) worst case time and O(n) space, where n is the input size. It's a stable sort, commonly used in sorting from disk.

MergeSort.java

import java.util.ArrayList;

/**
 *
 * @author anirvana
 */
public class MergeSort {

    public static void main(String[] args) {
        ArrayList<Integer> elements=new ArrayList<Integer>();
        elements.add(11);
        elements.add(20);
        elements.add(3);
        elements.add(11);
        elements.add(2);
        elements.add(13);
        
        mergeSort(elements,0, elements.size()-1);
        
        for(int i=0;i<elements.size();i++){
            System.out.println(elements.get(i));
        }
    }
    //Method to merge two adjacent sorted arrays elements[beg...mid] and elements[mid+d...end]
    public static void merge(ArrayList<Integer> elements, int beg, int mid, int end){
        ArrayList<Integer> sortedElms = new ArrayList<Integer>();         //Auxiliary array list
        int j=mid+1;
        int i=beg;
        
        while(i<=mid && j<=end){
            if(elements.get(i)<elements.get(j)) {
                sortedElms.add(elements.get(i));
                i++;
            }else{
                sortedElms.add(elements.get(j));
                j++;
            }
        }
        
        for(int k=i;k<=mid;k++) sortedElms.add(elements.get(k));
        
        for(int k=0;k<sortedElms.size();k++) {
            elements.set(beg+k, sortedElms.get(k));
        }
    }
    
    public static void mergeSort(ArrayList<Integer> elements, int beg, int end){
        if(beg>=end) return;
                
        int mid=beg+(end-beg)/2;
        mergeSort(elements,beg,mid);
        mergeSort(elements,mid+1,end);
        merge(elements, beg, mid, end);
        
    }
    
}