Bottom Up Merge Sort Java Implementation

Bottom up merge sort sorts the array without using recursion. It is 10% slower than the top down (recursive) mergesort. The idea is to start sorting the array elements from the start in groups of 2, 4, 8, 16, and so on (powers of two). So that the effect is the same as the recursive algorithm.
Here is a trace for sorting numbers 13,12, ..., 1

 

Source:

import java.util.Arrays;

public class BottomUpMergeSort {

    public static void merge(int[] orig, int[] aux, int start, int mid, int end) {
        int i, j, z = start; 
        
        if(orig[mid] <= orig[mid+1])return; 
        
        for(i=start, j = mid+1; i!=mid+1 || j!=end+1;){
            if(i==mid+1)               while(j!=end+1){ aux[z++] = orig[j++]; }
            else if(j==end+1)          while(i!=mid+1){ aux[z++] = orig[i++]; }
            else if(orig[i]<=orig[j])  aux[z++] = orig[i++];
            else                       aux[z++] = orig[j++];
        }    
        System.out.println(Arrays.toString(orig));
        System.out.println("start = "+start+" mid = "+mid+" end = "+end);
        System.out.println(Arrays.toString(aux)+"\n");
        System.arraycopy(aux, start, orig, start, end-start+1);
    }

    public static void sort(int[] orig, int[] aux, int start, int end) {
        int N = orig.length;
        for (int sz = 1; sz < N; sz *= 2) {
            for (int lo = 0; lo < N - sz; lo += sz + sz) {
                merge(orig, aux, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N-1));
            }
        }
    }

    public static void main(String[] args) {
        int array[] = {11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1};
        int aux[] = new int[array.length];
        sort(array, aux, 0, array.length - 1);
    }
}

lo < N - sz 
takes care to see that the mid value falls before end. 

lo < N - sz
lo + sz < N
lo + sz - 1 < N - 1
mid < N - 1

Math.min() takes care to see that end does not extend beyond the last index.

Output:

[11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
start = 0 mid = 0 end = 1
[10, 11, 0, 0, 0, 0, 0, 0, 0, 0, 0]
[10, 11, 9, 8, 7, 6, 5, 4, 3, 2, 1]
start = 2 mid = 2 end = 3
[10, 11, 8, 9, 0, 0, 0, 0, 0, 0, 0]
[10, 11, 8, 9, 7, 6, 5, 4, 3, 2, 1]
start = 4 mid = 4 end = 5
[10, 11, 8, 9, 6, 7, 0, 0, 0, 0, 0]
[10, 11, 8, 9, 6, 7, 5, 4, 3, 2, 1]
start = 6 mid = 6 end = 7
[10, 11, 8, 9, 6, 7, 4, 5, 0, 0, 0]
[10, 11, 8, 9, 6, 7, 4, 5, 3, 2, 1]
start = 8 mid = 8 end = 9
[10, 11, 8, 9, 6, 7, 4, 5, 2, 3, 0]
[10, 11, 8, 9, 6, 7, 4, 5, 2, 3, 1]
start = 0 mid = 1 end = 3
[8, 9, 10, 11, 6, 7, 4, 5, 2, 3, 0]
[8, 9, 10, 11, 6, 7, 4, 5, 2, 3, 1]
start = 4 mid = 5 end = 7
[8, 9, 10, 11, 4, 5, 6, 7, 2, 3, 0]
[8, 9, 10, 11, 4, 5, 6, 7, 2, 3, 1]
start = 8 mid = 9 end = 10
[8, 9, 10, 11, 4, 5, 6, 7, 1, 2, 3]
[8, 9, 10, 11, 4, 5, 6, 7, 1, 2, 3]
start = 0 mid = 3 end = 7
[4, 5, 6, 7, 8, 9, 10, 11, 1, 2, 3]
[4, 5, 6, 7, 8, 9, 10, 11, 1, 2, 3]
start = 0 mid = 7 end = 10
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]

Merge Sort Implementation with minor Improvements [Java]

Here is the basic merge sort algorithm implementation to which we will be adding some improvements:

Source: 

import java.util.Arrays;
 
public class MergeSort {

    public static void merge(int[] orig, int[] aux, int start, int mid, int end) {
        int i, j, z = start;  
        
        for(i=start, j = mid+1; i!=mid+1 || j!=end+1;){
            if(i==mid+1)               while (j!=end+1){ aux[z++] = orig[j++]; }
            else if(j==end+1)          while (i!=mid+1){ aux[z++] = orig[i++]; }
            else if(orig[i]<=orig[j])  aux[z++] = orig[i++];
            else                       aux[z++] = orig[j++];
        }   
        System.arraycopy(aux, start, orig, start, end-start+1);
    }

    public static void sort(int[] orig, int[] aux, int start, int end) {
        if (start >= end) return;
        int mid = (start + end) / 2;
        sort(orig, aux, start, mid); 
        sort(orig, aux, mid + 1, end); 
        merge(orig, aux, start, mid, end);
    }

    public static void main(String[] args) {
        int array[] = {5, 4, 3, 2, 1};
        int aux[] = new int[array.length]; 
        sort(array, aux, 0, array.length-1);
        System.out.println(Arrays.toString(array));
    }
}

Improvements that we can add:

1. Skip merge procedure if the elements in the two sorted halves to merge are already in ascending order (i.e. if firstHalf's end element <= secondHalf's first element so no merge is needed at all).
2. We can avoid copying back from auxiliary array every time merge is called by interchanging the roles of original array and auxiliary array during recursion. (The final result will be stored in the auxiliary array.)

Source: 

import java.util.Arrays;

public class MergeSort2 {

    public static void merge(int[] orig, int[] aux, int start, int mid, int end) {
        int i, j, z = start; 
        
        if(orig[mid] <= orig[mid+1])return; //Point #1
        
        for(i=start, j = mid+1; i!=mid+1 || j!=end+1;){
            if(i==mid+1)               while(j!=end+1){ aux[z++] = orig[j++]; }
            else if(j==end+1)          while(i!=mid+1){ aux[z++] = orig[i++]; }
            else if(orig[i]<=orig[j])  aux[z++] = orig[i++];
            else                       aux[z++] = orig[j++];
        }    
    }

    public static void sort(int[] orig, int[] aux, int start, int end) {
        if (start >= end) return;
        int mid = (start + end) / 2;
        sort(aux, orig, start, mid);        //Point #2
        sort(aux, orig, mid + 1, end);      
        merge(orig, aux, start, mid, end);
    }

    public static void main(String[] args) {
        int array[] = {5, 4, 3, 2, 1};
        int aux[] = new int[array.length];
        System.arraycopy(array, 0, aux, 0, array.length);  //Be careful, both arrays must be the same initially!
        sort(array, aux, 0, array.length-1);
        System.out.println(Arrays.toString(aux));
    }
}

Merge Sort Implementation In Java

This program implements Merge Sort Algorithm.

Merge sort (also commonly spelled mergesort) is an O(n log n) comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the implementation preserves the input order of equal elements in the sorted output. Mergesort is a divide and conquer algorithm. Have a quick read here if you like. 

Code:

import java.util.Arrays;

public class MergeSort { 
    
    public static void mergeSort(int[] orig){
        int temp[] = new int[orig.length];
        mergeSorter(0, orig.length-1, orig, temp);
    }
    
    private static void mergeSorter(int beg, int end, int[] orig, int[] temp) {
        if (beg == end) {
            return;
        }  
        mergeSorter(beg, (beg + end) / 2, orig, temp); 
        mergeSorter((beg + end) / 2 + 1, end, orig, temp);  
        merge(beg, end, orig, temp); 
        System.arraycopy(temp, beg, orig, beg, (end-beg+1));
    } 
    
    private static void merge(int beg, int end, int[] orig, int[] temp){
        int s1 = beg;           //first half starting position
        int e1 = (beg+end)/2;   //first half ends here
        int s2 = (beg+end)/2+1; //second half starts here
        int e2 = end;           
        
        int i = beg, l = s1, r = s2;
        while(l<=e1 && r<=e2){ 
            if (orig[l] >= orig[r]) {
                temp[i] = orig[r];  
                r++;
            } else if (orig[l] < orig[r]) {
                temp[i] = orig[l];  
                l++;
            } 
            i++;
        } 

        if (l == e1+1) { 
            System.arraycopy(orig, r, temp, i, e2-r+1);  
        } else if (r == e2+1) { 
            System.arraycopy(orig, l, temp, i, e1-l+1); 
        }   
    }
    
    public static void main(String[] args) { 
        int[] input = new int[]{5, 6, 3, 2, 2, 9, 9, 0};    //test array
        MergeSort.mergeSort(input);
        System.out.print(Arrays.toString(input));
    }
}

Output:
[0, 2, 2, 3, 5, 6, 9, 9] 

as expected.