Merge Sort

The merge sort algorithm closely follows the divide-and-conquer paradigm. Intuitively,
it operates as follows.

Divide: Divide the n-element sequence to be sorted into two subsequences of n=2
elements each.
Conquer: Sort the two subsequences recursively using merge sort.
Combine: Merge the two sorted subsequences to produce the sorted answer.

The recursion “bottoms out” when the sequence to be sorted has length 1, in which
case there is no work to be done, since every sequence of length 1 is already in
sorted order.
The key operation of the merge sort algorithm is the merging of two sorted
sequences in the “combine” step.

MERGE-SORT (A, l, r)
1                    if l < r
2                          mid =  [ (l + r) / 2 ]
3                          SORT (A, l , m )
4                          SORT (A, m + 1,  r)
5                          MERGE (A, l, m, r)

/** * Created by Ali on 9/21/2016. */

class MergeSort {
    public static void main(String args[]) {
        int arr[] = {12, 11, 13, 5, 6, 7};
        System.out.println("Given Array");
        printArray(arr);

        MergeSort ob = new MergeSort();
        ob.sort(arr, 0, arr.length-1);
        System.out.println("\nSorted array");
        printArray(arr);
    }
    

// Merges two subarrays of arr[]. First subarray is arr[l..m] Second subarray is arr[m+1..r]    

void merge(int arr[], int l, int m, int r) {
        int n1 = m - l + 1;
        int n2 = r - m;

        int[] L = new int[n1];
        int[] R = new int[n2];

        for (int i = 0; i < n1; i++) {
            L[i] = arr[l + i];
        }
        for (int j = 0; j < n2; j++) {
            R[j] = arr[m + 1 + j];
        }

        int k = l;
        int i=0 , j=0;
        while(i < n1 && j < n2) {
            if(L[i] < R[j]) {
                arr[k++] = L[i++];
            }else {
                arr[k++] = R[j++];
            }
        }

        while(i < n1){
            arr[k++] = L[i++];
        }
        while(j < n2){
            arr[k++] = R[j++];
        }
    }

    void sort(int arr[], int l, int r){

        if(l < r) {
            int m = (l+r)/2;

            sort(arr, l , m);
            sort(arr, m+1, r);

            merge(arr, l, m, r);
        }
    }

    private static void printArray(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

Time complexity of Merge Sort is O(nLogn) in all 3 cases (worst, average and best) as merge sort always divides the array in two halves and take linear time to merge two halves.

Auxiliary Space: O(n)

Algorithmic Paradigm: Divide and Conquer

Stable: Yes

Applications of Merge Sort

1. Merge Sort is useful for sorting linked lists in O(nLogn) time.In case of linked lists the case is different mainly due to difference in memory allocation of arrays and linked lists. Unlike arrays, linked list nodes may not be adjacent in memory. Unlike array, in linked list, we can insert items in the middle in O(1) extra space and O(1) time. Therefore merge operation of merge sort can be implemented without extra space for linked lists.
   In arrays, we can do random access as elements are continuous in memory. Let us say we have an integer (4-byte) array A and let the address of A[0] be x then to access A[i], we can directly access the memory at (x + i*4). Unlike arrays, we can not do random access in linked list. Quick Sort requires a lot of this kind of access. In linked list to access i’th index, we have to travel each and every node from the head to i’th node as we don’t have continuous block of memory. Therefore, the overhead increases for quick sort. Merge sort accesses data sequentially and the need of random access is low.

Insertion Sort

It is a simple Sorting algorithm which sorts the array by shifting elements one by one. Following are some of the important characteristics of Insertion Sort.

1. It is better than Selection Sort and Bubble Sort algorithms.
2. Its space complexity is less, like Bubble Sorting, insertion sort also requires a single additional memory space.
3. It is Stable, as it does not change the relative order of elements with equal keys

How Insertion Sorting Works

Insertion Sort Fig-1

/**

 * Created by Ali on 9/5/2016.   

 * Uses: Insertion sort is uses when number of elements is small. 

 * Or when input array is almost sorted, only few elements are misplaced in complete big array. 

**/

public class InsertionSort {
    public static void main(String str[]) {
        int[] arr = new int[]{10,54,2,100,200,121,99,150,51,181};
        InsertionSort obj = new InsertionSort();
        int[] sortedArray = obj.insertionSort(arr);
        for (int i = 0; i < sortedArray.length; i++) {
            System.out.print(sortedArray[i] + " ");
        }
    }

    private int[] insertionSort(int[] arr) {
        for(int i=1; i < arr.length; i++) {
            int key = arr[i];
            int j = i - 1;
            while(j>=0 && arr[j] > key){
                arr[j+1] = arr[j];
                j--;
            }
            arr[j+1] = key;
        }
        return arr;
    }
}

Time Complexity: O(n*n)

Auxiliary Space: O(1)

Boundary Cases: Insertion sort takes maximum time to sort if elements are sorted in reverse order. And it takes minimum time (Order of n) when elements are already sorted.

Bubble Sort

Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order.

How Bubble Sorting Works

/** Created by Ali on 9/1/2016.

  * Bubble Sort that works by repeatedly swapping the adjacent elements 

  * if they are in wrong order.
  */

public class BubbleSort {

    public static void main(String str[]){
        int[] arr = new int[]{10,54,2,100,200,121,99,150,51,181};
        BubbleSort obj = new BubbleSort();
        int[] sortedArray = obj.bubbleSort(arr);
        for (int i = 0; i < sortedArray.length; i++) {
            System.out.print(sortedArray[i] + " ");
        }
    }

    private int[] bubbleSort(int[] unsortedArray) {
        int length = unsortedArray.length;
        for (int i = 0; i < length-1; i++) {
            for(int j = 0; j < length-i-1; j++) {
                if(unsortedArray[j] > unsortedArray[j+1]) {
                    swap(unsortedArray, j , j+1);
                }
            }
        }
        return unsortedArray;
    }

    // An optimized version of Bubble Sort    

    private int[] bubbleSortOptimized(int unsortedArray[]) {
        int i, j;
        int length = unsortedArray.length;
        boolean swapped;
        for (i = 0; i < length-1; i++) {
            swapped = false;
            for (j = 0; j < length-i-1; j++) {
                if (unsortedArray[j] > unsortedArray[j+1]) {
                    swap(unsortedArray, j , j+1);
                    swapped = true;
                }
            }
            // IF no two elements were swapped by inner loop, then break            if (swapped == false)
                break;
        }
        return unsortedArray;
    }

    private void swap(int[] array, int i1, int i2) {
        int temp;
        temp = array[i1];
        array[i1] = array[i2];
        array[i2] = temp;
    }
}

Worst and Average Case Time Complexity: O(n*n). Worst case occurs when array is reverse sorted.

Best Case Time Complexity: O(n). Best case occurs when array is already sorted.

Auxiliary Space: O(1)