In Detail : A Simple Mergesort In Java Along With Generics Implementation

    Mergesort is implemented by John Von Neumann in 1945. Even though very old, it is still used all the time in practice because this is one of the methods of choice for sorting. Mergesort is also preferred for sorting linked lists.

First i will start the discussion with an example, Let's see.

Consider you have a sheet of paper. First tear the paper into 2 pieces by making the sheet into half, then tear the 2 pieces into 4 pieces, do this for up to some extent. Now give a number to each piece of paper.

Take half of the pieces in one hand, another half to another hand and arrange them in order from lowest to highest.

Now we will see, How to sort these numbered pieces in ascending order.

1. Compare top sheets of two piles and place the less valued piece on the desk. Now the number of sheets is 1 less than total number of sheets before.
2. By continuing this procedure, you'll end up in the following situations
a. No pieces left in both hands
b. some pieces left in either left hand or right hand.

3.  Now you have already arranged pieces in prior. The only thing you have to do is remove each piece from hand and place on the desk.
4. Finally you can see all the pieces arranged in order from lowest to highest.

We can consider this simple example as inspiration for Mergesort.

In Mergesort the approach to solve the problem is divide and conquer. We would split the list of objects into half, sort the halves, and then merge the sorted halves together. This is the idea behind Mergesort

Conceptually Mergesort is one of the simple sorting algorithms, and has good performance both in the asymptotic sense and in empirical running time.

Mergesort follows a recursive approach to sort the problem set. Firt of all, it divides the list into two halves and sorts the right sub list and then sort the left sub list. Finally merges both sorted left and right sublists.

How Mergesort Works ?

    Merge sort splits the input Array into two subarrays. In reality we are not allocating memory to subarrays. In each recursive call, we will pass bounds of subarray to Mergesort method. Which inturn calculates mid position of sub array, and this division continues recursively until the begin index and end index are same i.e when the subarray contains only one element. This division process requires "logn" levels of recursion.
   
    With the help of temporary second array, Mergesort would merge subarrays. Note that this approach requires twice the amount of space than insertion sort, selection sort, & bubble sort, which is a serious disadvantage for Mergesort. It is possible to merge the subarrays without using a second array, but this is extremely difficult to do efficiently and is not really practical. 

Let's jump into the code analysis of Mergesort.

Implementation Of Mergesort :

    package sorting;
 
    public class Mergesort {
  
 // this represents input for Mergesort
 private int[] intArray = new int[20]; 
 // this represents temperory array for holding elements of input
       private int[] tempMergeArray = new int[20]; 
  
 public static void main(String[] args) {
  
     Mergesort ms = new Mergesort();
     // utility method for filling input array with random numbers
     ms.fillArray(); 
     // 0 represents start index, 19 represents end index
            // use inputArray.length ,if you don't know the length prior
     ms.mergeSort(0,19);
     // prints the sorted input array
     ms.printArray(); 
 }
 
 private void printArray() {
     System.out.println();
     for(int i = 0; i < intArray.length; i++) {
  System.out.print(" "+intArray[i]);
     }
   
 }

 private void fillArray() {
     for(int i = 0; i < intArray.length; i++) {
  intArray[i] = (int) (Math.random()*intArray.length);
     }  
 }
  
 private void mergeSort(int begin, int end) {
     int mid = (begin + end) / 2; // divide the input array into half
  
     /*incase of single element the indexes for begin and 
      * end are same. so already sorted*/
   
     if(begin == end) return;
     mergeSort(begin, mid); // sort the left sub array
     mergeSort(mid+1, end); // sort the right sub array
     merge(begin,mid,end);
   
 }
  
 private void merge(int begin, int mid, int end) {

            /*
      *copy all the elements from input array to helper 
      *array from given positions
       */
   
     for(int i = begin; i <= end; i++) {
   tempMergeArray[i] = intArray[i];
     }
  
     int left = begin; // first index in left array
     int right = mid + 1; // first index in right array 
   
     /*
      * Sorting the sub array occurs here   
      */
   
   for(int current = begin; current <= end; current++) {  
   
     /*
      *  this means all the elements in left sub array are over.
      *  therefore copy all the elements of right sub array 
      *  to main array.
      */
    
     if(left == mid+1) {
       intArray[current] = tempMergeArray[right++];    
     }
     /*
      * this means all the elements of right sub array are over.
      * Therefore copy all the elements of left sub array 
      * to main array.
      */
     else if( right > end) {
        intArray[current] = tempMergeArray[left++];
     } 
     /*
      * comparing first elements of left and right sub arrays,
      *  and then inserting into input array
      */   
     else if(tempMergeArray[left] < tempMergeArray[right]) {
         intArray[current] = tempMergeArray[left++];
     } else {
          intArray[current] = tempMergeArray[right++];
     }  
   
   } 
      }
} 

Implementation Of Mergesort That Supports Generic Array in Java :

  private > void mergeSortG(E[] inpArr, E[] tempArr,int begin, int end) 
  {
 int mid = (begin + end) /2;
 if(begin == end) {
         return ;    
 }
  
 mergeSortG(inpArr,tempArr,begin,mid);
 mergeSortG(inpArr,tempArr,mid+1,end);
 mergeG(inpArr,tempArr,begin,mid,end);
     
   }
  
   private > void mergeG(E[] inpArr, E[] tempArr,int begin, int mid, int end) {
 for(int i = begin; i <= end; i++) {
         tempArr[i] = inpArr[i];
 }
   
 int left = begin;
 int right = mid+1;
   
 for(int current = begin; current <= end; current++) {
     if(left == mid+1) {
  inpArr[current] = tempArr[right++];
     } else if(right > end) {
  inpArr[current] = tempArr[left++];
     } else if(tempArr[left].compareTo(tempArr[right]) < 0){
  inpArr[current] = tempArr[left++];
     } else {
  inpArr[current] = tempArr[right++];
     }
 }
   
   } 

When to use Mergesort?

     Mergesort is used when the data structure doesn't support random access, such as linked lists, double linked lists. It is also widely used for external sorting, where random access can be expensive compared to sequential access.
  
Properties Of Mergesort :

    1. O(n) for extra space
    2. O(n logn) - Running time
    3. stable - runnint time is same in all cases

Measuring Time Complexity Of Insertion Sort :

    Analysis of Mergesort is straightforward, despite the fact that it is a recursive algorithm. The merging part takes time O(i) where i is the total length of two subarrays being merged. The array to be sorted is repeatedly split in half until subarrays of size 1 are reached, at which time they are merged to be of size 2, these merged to subarrays of size 4 and so on. Thus the depth of the recursion is logn for n elements.
  
    The first level of recursion can be though of as working on one array of size n, the next level working on two arrays of size n/2, the next on four arrays of size n/4, and so on. The bottom of the recursion has n arrays of size 1. Thus, n arrays of size 1 are merge ( requiring O(n) total steps), n/2 arrays of size 2 (again requiring O(n) total steps), and so on. At each of the log n levels of recursion, O(n) work is done, for a total cost of O(n*logn). This cost is unaffected by the relative order of the values being sorted, thus this analysis holds for the best, average, worst cases.