Bucket Sort

Amazon Question: Given an array with 3 distinct elements, sort the elements in O(n) complexity
Input: 1,3,1,2,3,1,2,2,3
Output: 1, 1, 1, 2, 2, 2, 3, 3, 3


import java.util.ArrayList;

public class BucketSort {
    ArrayList> bucket;
    private int count;
    public BucketSort(int unique_int_count) {
        this.count = unique_int_count;
        this.bucket = new ArrayList>();
        for(int i=0; i < this.count; i++) {
            bucket.add(new ArrayList());
    }
    public ArrayList Sort(ArrayList input)    {
        for(int c:input)    {
            if(c==1)    {
                bucket.get(0).add(c);
            }    else if(c==2)    {
                bucket.get(1).add(c);
            }    else    {
                bucket.get(2).add(c);
            }
        }
        ArrayList sorted_output = new ArrayList<>();
        for(int i=0; i < count; i++) {
            sorted_output.addAll(bucket.get(i));
        return sorted_output;
    }
    @Override
    protected void finalize() throws Throwable {
        bucket=null;
        super.finalize();
    }
}
//----------------------Main Method------------------------
    public static void main(String[] args) {
        BucketSort b = new BucketSort(3);
        ArrayList input = new ArrayList();
        input.add(1);
        input.add(3);
        input.add(1);
        input.add(2);
        input.add(3);
        input.add(1);
        input.add(2);
        input.add(2);
        input.add(3);
        System.out.println(b.Sort(input));
    }

Quick Sort

import java.util.Random;

public class QuickSort {
    int[] a;
    public QuickSort(int[] a) {
        this.a = a;
    }
    public int[] QSort()    {
        QSort(this.a, 0, this.a.length-1);
        return a;
    }
    private void QSort(int[] a, int startIndex, int endIndex)    {
        if(startIndex<endIndex)    {
            int PartionIndex = RandomizedPartition(startIndex, endIndex);
            QSort(a, startIndex, PartionIndex-1);
            QSort(a, PartionIndex+1, endIndex);
        }
    }
    private int RandomizedPartition(int startIndex, int endIndex)    {
        /* Worst Case of QuickSort is O(n^2)
        The possibility for WorstCase in QuickSort is very low
        RandomizedPartition will help reducing the probability of the occurrence of worst case*/
        int PivotIndex=new Random().nextInt(endIndex-startIndex)+startIndex;
        swap(PivotIndex, endIndex);
        return Partition(startIndex, endIndex);
    }
    private int Partition(int startIndex, int endIndex)    {
        int Pivot=a[endIndex];
        int PivotIndex=startIndex;
        for(int i=startIndex; i<endIndex; i++)    {
            if(a[i]<=Pivot)    {
                swap(i, PivotIndex);
                PivotIndex++;
            }
        }
        swap(PivotIndex, endIndex);
        return PivotIndex;
    }
    private void swap(int IndexA, int IndexB)    {
        int temp=a[IndexA];
        a[IndexA]=a[IndexB];
        a[IndexB]=temp;
    }
}

Selection Sort

    public int[] SelectionSort(int[] a)    {
        for(int i=0; i<a.length; i++)    {
            int min=i;
            for(int j=i+1; j<a.length; j++)    {
                if(a[j]<=a[min])
                    min=j;
            }
            int temp=a[i];
            a[i]=a[min];
            a[min]=temp;
        }
        return a;
    }

Insertion Sort

    public int[] InsertionSort(int[] input)    {
        for(int i=1; i<input.length; i++)    {
            int val=input[i];
            int hole=i;
            while(hole>0 && val<input[hole-1])    {
                input[hole]=input[hole-1];
                hole--;
            }
            input[hole]=val;
        }
        return input;
    }

Bubble Sort

    public int[] BubbleSort(int[] input)    {
        int size=input.length;
        for(int i=0; i<size; i++)    {
            boolean flag = true;
            int s=size-i-1;
            for(int j=0; j<s; j++)    {
                if(input[j]>=input[j+1])    {
                    flag=false;
                    input[j] = input[j]+input[j+1];
                    input[j+1] = input[j]-input[j+1];
                    input[j] = input[j]-input[j+1];
                }
            }
            if(flag) break;
        }
        return input;
    }

Merge Sort

    public int[] MergeSort(int[] a)    {
        int mid = a.length/2;
        if(mid<1)    return a;
        int[] left = new int[mid];
        int i=0;
        for(; i<left.length; i++)
            left[i]=a[i];
        left = MergeSort(left);
        int[] right = new int[(a.length%2==1)?(mid+1):mid];
        for(int j=0; j<right.length; j++)    {
            right[j]=a[i];
            i++;
        }
        right = MergeSort(right);
        return Merge(left, right);
    }
    private int[] Merge(int[] left, int[] right)    {
        int i, j, k;    i=j=k=0;
        int[] merged = new int[left.length+right.length];
        while(i<left.length && j<right.length)    {
            if(left[i]<=right[j])    {
                merged[k]=left[i];
                i++;
            }    else if(left[i]>right[j])    {
                merged[k]=right[j];
                j++;
            }
            k++;
        }
        while(i<left.length)    {
            merged[k]=left[i];
            i++; k++;
        }
        while(j<right.length)    {
            merged[k]=right[j];
            j++; k++;
        }
        return merged;
    }

Sort a Stack using one additional Stack

    public Stack<Integer> SortStack(Stack<Integer> input)    {
        if(input.isEmpty())    return input;
        Stack<Integer> buffer = new Stack<Integer>(); //Buffer Stack
        while(!input.isEmpty())    {
            int temp = input.pop();
            if(!buffer.isEmpty() && temp<buffer.peek())
                input.push(buffer.pop());
            buffer.push(temp);
        }
        return buffer;
    }


This Code doesn't work all the time
Input: [5, 7, 8, 9, 6, 0, 2]
Output: [0, 2, 6, 8, 7, 5, 9]