CodingInterview.java

import java.util.Random;


public class CodingInterview {
  
	public static void swap(int[] array, int src, int dest){
		int temp = array[dest];
		array[dest] = array[src];
		array[src] = temp;
	}
	
	public static int partition(int[] array, int left, int right, 
			int pivotIndex){
		int pivotValue = array[pivotIndex];
    	swap(array, pivotIndex, right);
    	int storeIndex = left;
    	for(int i = left; i < right; i++){
    		if( array[i] < pivotValue){
            	swap(array, i, storeIndex);
            	storeIndex++;
    		}
    	}
    	swap(array, storeIndex, right);
    	return storeIndex;
	}
    	
	//option: 0 is first element, 1 is last element, or 2 for random pivot
    public static void quicksort(int[] array, int left, int right,
    		int option){
    
    	if(left < 0 && right >= array.length){
    		return;
    	}
    	
        if(left < right){
        	int pivot;
        	switch(option){
        		case 0:
        			pivot = left;
        			break;
        		case 1:
        			pivot = right;
        			break;
        		case 2:
        			Random random = new Random();
        			pivot = random.nextInt(right-left+1) + left;
        			break;
        		default:
        			pivot = left;
        			break;
        	}

            pivot = partition(array, left, right, pivot);
            quicksort(array, left, pivot - 1, option);
            quicksort(array, pivot + 1, right, option);
        }
    }
	
	public static void main(String[] args){
		int[] same = {1,1,1,1,1,1,1,1,1,1};
		int[] rand = {3,10,6,4,1,9,0,8,2,7,5};
		int[] sort = {0,1,2,3,4,5,6,7,8,9,10};
		quicksort(same,0,same.length - 1,0);
		for (int i = 0; i < same.length; i++) {
			System.out.println(same[i]);
		}
		quicksort(rand,0,rand.length - 1,0);
		for (int i = 0; i < rand.length; i++) {
			System.out.println(rand[i]);
		}
		quicksort(sort,0,sort.length - 1,0);
		for (int i = 0; i < sort.length; i++) {
			System.out.println(sort[i]);
		}
	}
}

quicksort.txt

Quicksort uses a pivot to base the sort, then goes down in the sublist.  A merge sort breaks down the list into its smallest elements, sorts and moves back up to build the original list.  Quicksort also compares to only one element at wch level, where merge sort compares the begining element of both list.  Quicksort also doesn't require additional memory where merge sort does in most implementations.