Merge Sort Practice

Merge sort is divide and conquer algorithm. it divides a problem into sub problems, and resolved the sub problems the first, then goes back to resolve problem based on resolved subproblems.

The idea of merge sort is to divide the list or array into smaller list or arrays until it can no longer be divided, that is, an one element array or list, then sort the divided array or list and merge them into sorted array or list to resolve original problem. the array or list with one element is considered as sorted.

Below is my practice on this algorithm with Java implementation. Array is passed by reference.

package array;

public class MergeSort {


public static void main(String[] args) {
int[] intOriginal = {0,10,32,3,44,15};
arrayTest(intOriginal);
for(int i=0;i System.out.println(intOriginal[i]);
mergeSort(intOriginal);
for(int i=0;i System.out.println(intOriginal[i]);
}
//this is to verify array is passed by reference
public static void arrayTest(int[] intA){
if (intA==null )return;
for(int i=0;i intA[i]+=1;

}
public static void mergeSort(int[] intA){
//array with one element is considered as sorted
if (intA==null||intA.length<2 p="" return=""> //longer than 1, then it is not sorted and we will try to sort it
//divide and conquer.
//divide the array into two subarrays. seperated from middle.
int mid = intA.length/2;
int[] leftA = new int[mid];
int[] rightA = new int[intA.length-mid];
System.arraycopy(intA, 0, leftA, 0, mid);
System.arraycopy(intA, mid, rightA, 0, intA.length-mid);
//do the same merge sort on the left and right subarrays
mergeSort(leftA);
mergeSort(rightA);
//after sorting left and right array, we need to merge the sorted array into original array
//this step does both sort and merge
mergeSortedArray(leftA,rightA,intA);
}
//content in intA can be overridden
public static void mergeSortedArray(int[] leftA,int[] rightA,int[] intA){
if(leftA==null||rightA==null || intA==null)return;
int i=0,j=0,k=0;
//it stops when one array is done the first
while(i if(leftA[i]<=rightA[j]){
intA[k]=leftA[i];
i++;
}
else{
intA[k] = rightA[j];
j++;
}
k++;
}
//then merge rest of array to target array
while(i intA[k]=leftA[i];
i++;k++;
}
while(j intA[k]=rightA[j];
j++;k++;
}
}

}