Merge Sort is a sorting technique based on divide and conquer
technique with comparison. 

Conceptually, a merge sort works as follows :

i) Divide the unsorted list into n sublists, each containing 1 element (a list
of 1 element is considered sorted).

ii) Repeatedly merge sublists to produce new sublists until there is only 1
sublist remaining. This will be the sorted list.

Merge sort - Visualization

 

Worst Case performance: O (n log n)

Best case Performance: O (n log n) for typical O(n) natural
variant

Average performance:  O(n log n)

Worst case space complexity : O(n) 

Merge Sort

Merge Sort Pseudocode and Algorithm:

MergeSort
(Array(First..Last))

Begin

If Array contains only one element Then

     Return Array

Else

     Middle= ((Last + First)/2) rounded
down to the nearest integer

     LeftHalfArray =
MergeSort(Array(First..Middle))

     RightHalfArray =
MergeSort(Array(Middle+1..Last))

     ResultArray = Merge(LeftHalfArray,
RightHalfArray)

     Return ResultArray

EndIf

End MergeSort

Java Program for Merge Sort:

import java.util.Scanner;

public class MergeSort

{

    public static void sort(int[] a, int low, int high)

    {

        int N = high - low;

        if (N <= 1)

            return;

        int mid = low + N / 2;

        sort(a, low, mid);

        sort(a, mid, high);

        int[] temp = new int[N];

        int i = low, j = mid;

        for (int k = 0; k < N; k++)

        {

            if (i == mid)

                temp[k] = a[j++];

            else if (j == high)

                temp[k] = a[i++];

            else if (a[j] < a[i])

                temp[k] = a[j++];

            else

                temp[k] = a[i++];

        }

        for (int k = 0; k < N; k++)

            a[low + k] = temp[k];

    }

    public static void main(String[] args)

    {

        Scanner scan = new Scanner(System.in);

        System.out.println("Merge Sort Test\n");

        int n, i;
        System.out.println("Enter number of integer elements");

        n = scan.nextInt();
        int arr[] = new int[n];
        System.out.println("\nEnter " + n + " integer elements");

        for (i = 0; i < n; i++)

            arr[i] = scan.nextInt();

        sort(arr, 0, n);
        System.out.println("\nElements after sorting ");

        for (i = 0; i < n; i++)

            System.out.print(arr[i] + " ");

        System.out.println();

    }

} 

Output :

Insertion sort is a simple sorting algorithm and it picks
one item at a time, sort the elements finally produce the sorted array.
Insertion sort is good for small size elements but not for large elements.

Insertion sort iterates though out the array and iterates
are equal to array size. Each iteration, insertion sort removes one element
from the input data and finds the location it belongs within the sorted list,
and inserts it there. It repeats the same until end of the input array.  Sorting typically done in place by comparing
the each element and at every position and check there is any value largest against
it.  If larger element found it leaves
the element in place and moves to the next and incase of smaller it finds the
correct position within the sorted list, and place it there. 

However, advantages of Insertion Sort are that it is
efficient for (quite) small data sets, adaptive for data sets that are already
substantially sorted, stable (i.e. does not change the relative order of
elements with equal keys), In-place ( i.e. only requires a constant amount O(1)
of additional memory space) and online (i.e. can sort a list as it receives
it).

Insertion Sort example

Worst Case Performance: 
O(n²) comparisons

Best Case Performance: O(n) comparisons

Average Case Performance: O(n²)
comparisons

Worst Case space complexity: O(n) total
and O(1) auxiliary

Algorithm for Insertion Sort:

// Sort an arr[] of size n

insertionSort(arr, n)

Loop from i = 1 to n-1.

……a) Pick element arr[i] and insert it into sorted sequence arr[0…i-1]

Pseudo code for Insertion Sort:

for
i ← 1 to length(A)

    j ← i

    while j > 0 and A[j-1] > A[j]

        swap A[j] and A[j-1]

        j ← j - 1

    end while

end
for

Let us see the below example for Insertion sort:

2, 4, 9, 6, 23, 12, 34, 0, 1,

2, 4, 9, 6, 23, 12, 34, 0, 1,

2, 4, 6, 9, 23, 12, 34, 0, 1,

2, 4, 6, 9, 23, 12, 34, 0, 1,

2, 4, 6, 9, 12, 23, 34, 0, 1,

2, 4, 6, 9, 12, 23, 34, 0, 1,

0, 2, 4, 6, 9, 12, 23, 34, 1,

0, 1, 2, 4, 6, 9, 12, 23, 34,

 

Program for Insertion Sort in  Java:

import java.util.Scanner;
public class InsertionSort
{
    public static void sort( int arr[] )
    {
        int size = arr.length;
        int i, j, temp;
        for (i = 1; i< size; i++)
        {
            j = i;
            temp = arr[i];   
            while (j > 0 && temp < arr[j-1])
            {
               arr[j] = arr[j-1];
                j = j-1;
            }
            arr[j] = temp;           
        }       
    }   
    public static void main(String[] args)
    {
        Scanner input = new Scanner( System.in );       
        System.out.println("Insertion Sort over the given input\n");
        int n, i;
        /* Accept a number for sorting elements */
        System.out.println("Enter size of integer elements");
        n = input.nextInt();
        /* Create integer array on n elements */
        int arr[] = new int[ n ];
        /* Accept elements */
        System.out.println("\nEnter "+ n +" integer elements");
        for (i = 0; i < n; i++)
            arr[i] = input.nextInt();
       /* Call method sort */
        sort(arr);
        /* Print sorted Array */
        System.out.println("\nElements after sorting ");       
        for (i = 0; i < n; i++)
        System.out.print(arr[i]+" ");           
        System.out.println();                    
    }   
}

Output is :

3, 12, 34, 0, 1,

2, 4, 9, 6, 23, 12, 34, 0, 1,

2, 4, 6, 9, 23, 12, 34, 0, 1,

2, 4, 6, 9, 23, 12, 34, 0, 1,

2, 4, 6, 9, 12, 23, 34, 0, 1,

2, 4, 6, 9, 12, 23, 34, 0, 1,

0, 2, 4, 6, 9, 12, 23, 34, 1,

0, 1, 2, 4, 6, 9, 12, 23, 34, - See more at:
http://www.java2novice.com/java-interview-programs/insertion-sort/#sthash.KEc6oyNn.dpuf

2,
4, 9, 6, 23, 12, 34, 0, 1,

2, 4, 9, 6, 23, 12, 34, 0, 1,

2, 4, 6, 9, 23, 12, 34, 0, 1,

2, 4, 6, 9, 23, 12, 34, 0, 1,

2, 4, 6, 9, 12, 23, 34, 0, 1,

2, 4, 6, 9, 12, 23, 34, 0, 1,

0, 2, 4, 6, 9, 12, 23, 34, 1,

0, 1, 2, 4, 6, 9, 12, 23, 34, - See more at:
http://www.java2novice.com/java-interview-programs/insertion-sort/#sthash.KEc6oyNn.dpuf

Bucket sort is a sorting algorithm also knows as bin sort,
it works with distributing elements of an array into a number of buckets. 

A bucket is most commonly a type of data buffer or a type of
document in which data is divided into regions. Elements or contents in the
bucket are unsorted and size of the bucket is fixed at the time of creation.

A bucket has states of empty, non-empty, full or partly
full, and overflows.

Each bucket is sorted individually, using any sorting
algorithm or bucket sorting.  Basically
bucket sort is distribution sort and it is cousin of radix sort. Bucket sort
can be implemented with comparisons and therefore can also be considered a
comparison sort algorithm. 

Worst – case performance:      O(n²)

Best Case Performance:  
        Ω(n+k)

Average Performance:            
 θ(n+k)

Worst case space complexity:  O(n.k)

  

Pseudo code of Bucket sort:

 

function
bucketSort(array, n) is

  buckets ← new array of n empty lists

  for i = 0 to (length(array)-1) do

    insert array[i] into
buckets[msbits(array[i], k)]

  for i = 0 to n - 1 do

    nextSort(buckets[i]);

  return the concatenation of
buckets[0], ...., buckets[n-1]

Please look at the instance:

 

Given Series is: [34,12,45,23,1,3,4,36,19,20,28,56,67,48,59]

Distribute these elements into buckets/bins like below

 

Distribution of given Elements in Buckets

 In the above picture elements are distributed among the
bins/buckets

Sorting in Each Bin

Elements are sorted in each bin/bucket.

Implement bucket sort in java:

import java.util.*;

public class BucketSort{

   public static void
sort(int[] a, int limit) {

      int [] bucket=new
int[limit+1];

      for (int i=0;
i<bucket.length; i++) {

         bucket[i]=0;

      }

      for (int i=0;
i<a.length; i++) {

        
bucket[a[i]]++;

      }

      int outPos=0;

      for (int i=0;
i<bucket.length; i++) {

         for (int j=0;
j<bucket[i]; j++) {

           
a[outPos++]=i;

         }

      }

   } 

   public static void
main(String[] args) {

      int limit=5;

      int [] data=
{5,3,0,2,4,1,0,5,2,3,1,4};

     
System.out.println("Before: " + Arrays.toString(data));

      sort(data,limit);

     
System.out.println("After: 
" + Arrays.toString(data));

   }

}

Out put of the above program is: