public class LinearSearch {
    /**
     * @param a Array of unsorted integers
     * @param val The value to search for
     * @return Array's index if found; -1 if not found. 
     */
    private static int search(int[] a, int val)
    {
        for(int k=0; k<a.length; k++){
            if(val==a[k])
                return k;
        }
        return -1;  // not found
    }
}

public class BinarySearch {
    /**
     * @param a Array of sorted integers
     * @param val The value to search for
     * @param lo Low index of array
     * @param hi High index of array
     * @return Array's index if found; -1 if not found. 
     */
    public static int search(int[] a, int val, int lo, int hi)
    {
        while(lo<=hi){
            int mid = (lo + hi) >>> 1;
            int midVal = a[mid];
            if(val == midVal){
                return mid;
            }else if(val < midVal){
                hi = mid-1;
            }else{
                lo = mid+1;
            }
        }
        return -1;  // not found
    }

    /**
     * @param a Array of sorted integers
     * @param val The value to search for
     * @param lo Low index of array
     * @param hi High index of array
     * @return Array's index if found; -1 if not found. 
     */
    public static int searchWithRecursive(int[] a, int val, int lo, int hi)
    {
        int mid = (lo + hi) >>> 1;
        int midVal = a[mid];
        if(val == midVal)
            return mid;
        
        if(val < midVal)
            return searchWithRecursive(a, val, lo, mid-1);
        else
            return searchWithRecursive(a, val, mid+1, hi);
    }

/**
 *  Average case performance: O(n^2)
 *  Best case performance:    O(n)
 *  Worst case performance:   O(n^2)
 */
public class BubbleSort {

    /**
     * @param a Array of integers which are sorted when returns.
     */
    public static void sort(int[] a)
    {
        if(a==null||a.length==0)
            return;
        
        int temp;
        for(int k=a.length; k>1; k--){
            for(int j=1; j<i; j++){
                if(a[j]<a[j-1]){
                    temp = a[j-1]; 
                    a[j-1] = a[j];
                    a[j] = temp;
                }
            }
        }
    }
}

/**
 *  Average case performance: O(n^2)
 *  Best case performance:    O(n)
 *  Worst case performance:   O(n^2)
 */
public class InsertionSort {

    /**
     * @param a Array of integers which are sorted when returns.
     */
    public static void sort(int[] a)
    {
        if(a==null||a.length==0)
            return;
        
        int temp;
        for(int k=1; k<a.length; k++){
            temp = a[k];
            int j;
            for(j=i; j>0 && a[j-1]>temp; j--){
                a[j]=a[j-1];
            }
            a[j]=temp;
        }
    }
}

/**
 *  Average case performance: O(nlogn)
 *  Best case performance:    O(nlogn)
 *  Worst case performance:   O(nlogn)
 */
public class HeapSort {
    
    /**
     * @param a Array of integers which are sorted when returns.
     */
    public static void sort(int[] a){
        
        /* Insertion onto heap */
        for(int k=0; k<a.length; k++){
            int n = k;
            while(n>0){
                int p = (n-1)/2; // parent
                if(a[n]>a[p]){
                    swap(a, n, p);
                    n = p;
                }else{
                    break;
                }
            }
        }
        
        /* Removal from heap */
        for(int k=a.length-1; k>0; k--){
            swap(a, 0, k);
            maxHeap(a, k, 0);
        }
    }
    
    /**
     * @param a Array of integers
     * @param size The heapsize
     * @param p The starting point/parent to heapify
     */
    private static void maxHeap(int[] a, int size, int p)
    {
        int left  = 2*p + 1;
        int right = left + 1;
        
        // leaf node
        if(left>=size)
            return;
        // node with only left child
        if(right>=size){
            if(a[left]>a[p]){
                swap(a, left, p);
            }
            return;
        }
        
        // find the largest among node, left child and right child.
        int largest = p;
        if(a[left]>a[p])
            largest = left;
        if(a[right]>a[largest])
            largest = right;
        
        if(largest!=p){
            swap(a, p, largest);
            maxHeap(a, size, largest);
        }
    }
    
    private static void swap(int[] a, int j, int k) {
        int temp = a[j];
        a[j] = a[k];
        a[k] = temp;
    }

}

/**
 *  Average case performance: O(nlogn)
 *  Best case performance:    O(nlogn)
 *  Worst case performance:   O(nlogn)
 */
public class MergeSort {

    /**
     * @param a Array of integers which are sorted when returns.
     */
    public static void sort(int[] a){
        int[] help = new int[a.length];
        mergeSort(a, help, 0, a.length);
    }
    
    /**
     * @param src Array of integers
     * @param dest Helper array
     * @param low Low index of array
     * @param high High index of array
     */
    private static void mergeSort(int[] src, int[] dest, int low, int high)
    {
        int len = high - low;
        
        if(len==1){
            dest[low] = src[low];
            return;
        }

        int mid = (low+high)>>>1;
        
        // split
        mergeSort(src, dest, low, mid);
        mergeSort(src, dest, mid, high);
        
        // merge
        int p1 = low;
        int p2 = mid;
        for(int k=low; k<high; k++){
            if(p1<mid&&p2<high){
                if(dest[p1]<=dest[p2]){  // '=' for stable
                    src[k] = dest[p1++];
                }else{
                    src[k] = dest[p2++];
                }
            }else if(p1<mid){
                src[k] = dest[p1++];
            }else if(p2<high){
                src[k] = dest[p2++];
            }
        }
        
        // copy back to dest
        for(int k=low; k<high; k++){
            dest[k] = src[k];
        }
    }    

}

/**
 *  Average case performance: O(nlogn)
 *  Best case performance:    O(nlogn)
 *  Worst case performance:   O(n^2)
 */
public class QuickSort {

    /**
     * @param a Array of integers which are sorted when returns.
     */
    public static void sort(int[] a){
        quickSort(a, 0, a.length-1);
    }
    
    /**
     * @param src Array of integers
     * @param first Low index of array
     * @param last High index of array
     */
    private static void quickSort(int[] a, int first, int last)
    {

        if(last<=first)
            return;
        
        int pivot = a[first];
        
        int pos = first;
        for(int k=first+1; k<=last; k++ ){
            if(a[k]<pivot){
                swap(a, ++pos, k);
            }else{
                // skip those ordered in nature
            }
        }
        swap(a, first, pos);

        // split without pivot
        quickSort(a, first, pos-1);
        quickSort(a, pos+1, last);
        
    }
    
    private static void swap(int[] a, int j, int k) {
        int temp = a[j];
        a[j] = a[k];
        a[k] = temp;
    }

}