Merge Sort

**
 * Merge sort is a sorting technique based on divide and conquer technique. With
 * worst-case time complexity being O(n log n), it is one of the most respected
 * algorithms.
 *
 * Merge sort first divides the array into equal halves and then combines them
 * in a sorted manner. Compared to insertion sort [O(n*2) worst-case time],
 * merge sort is faster. Trading a factor of n for a factor of lg n is a good
 * deal. On small inputs, insertion sort may be faster. But for large enough
 * inputs, merge sort will always be faster, because its running time grows more
 * slowly than insertion sorts.
 *
 * Stable: If 2 keys are same in input list then in sorted list also their order is same.
 *
 * O(n) extra space for arrays (as shown)
 *
 * O(lg(n)) extra space for linked lists
 *
 * O(nlg(n)) time
 *
 * Not adaptive
 *
 * Does not require random access to data
 *
 * Not in-place algorithms. (in-place algorithm take O(1) space)
 *
 * @author RAGHAV
 *
 */
public class MergeSort extends ProgrammingTools {

/**
* Main function that sorts arr[l..r] using merge()
*
* @param numbers
* @param temp
* @param left
* @param right
*/
public void sort(int numbers[], int left, int right) {

if (left < right) {
// Find the middle point
int mid = (right + left) / 2;

// Sort first and second halves
sort(numbers, left, mid);
sort(numbers, mid + 1, right);

// Merge the sorted halves
merge(numbers, left, mid, right);
}
}

/**
* Merges two subarrays of arr[]. First subarray is arr[l..m] Second subarray is
* arr[m+1..r]
*
* @param numbers
* @param left
* @param mid
* @param right
*/
private void merge(int[] numbers, int left, int mid, int right) {
// Find sizes of two subarrays to be merged
int sizeOfSubArray1 = mid - left + 1;
int sizeOfSubArray2 = right - mid;

//create temp arrays
int[] temp1 = new int[sizeOfSubArray1];
int[] temp2 = new int[sizeOfSubArray2];

//copy data to temp arrays
for(int i = 0; i < sizeOfSubArray1; i++) {
temp1[i] = numbers[left + i];
}
for(int j = 0; j < sizeOfSubArray2; j++) {
temp2[j] = numbers[mid + 1 + j];
}

//merge temp arrays

//initialize the indexes for temp arrays
int i = 0, j = 0;

//initialize index of merged subarray
int k = left;

while (i < sizeOfSubArray1 && j < sizeOfSubArray2) {
if (temp1[i] <= temp2[j]) {
numbers[k++] = temp1[i++];
} else {
numbers[k++] = temp2[j++];
}
}

//Copy remaining elements of temp1[] if any
while (i < sizeOfSubArray1) {
numbers[k++] = temp1[i++];
}

//Copy remaining elements of temp2[] if any
while (j < sizeOfSubArray2) {
numbers[k++] = temp2[j++];
}
}

public static void main(String... strings) {
int[] arr = { 7, 6, 23, 19, 10, 11, 9, 3, 15 };

System.out.print("Unsorted list : ");
printArray(arr);

MergeSort mergeSort = new MergeSort();
mergeSort.sort(arr, 0, arr.length - 1);
System.out.println();
System.out.print("Sorted list : ");
printArray(arr);
}
}

Time and Space Complexity:

Auxiliary Space: O(n)

Algorithmic Paradigm: Divide and Conquer

Sorting In Place: No in a typical implementation

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.
2. Inversion Count Problem
3. Used in External Sorting