Cognitame

'A man is none the less a slave because he is allowed to choose a new master once in a term of years. Neither are a people any the less slaves because permitted periodically to choose new masters. What makes them slaves is the fact that they now are, and are always hereafter to be, in the hands of men whose power over them is, and always is to be, absolute and irresponsible.' -Lysander Spooner, No Treason

# Merge Sort

by Ethan Glover, Sun, Oct 12, 2014 - (Edited) Tue, Nov 01, 2016

A fascinating divide-and-conquer algorithm that recursively splits an array into two halves until you are left with two single elements to compare. Once that is done, the individual sorted elements are merged together to create one sorted array.

public class MergeSort {
// Test method
public static void main(String[] args) {
int[] list = {2, 3, 2, 5, 6, 1, -2, 3, 14, 12};
mergeSort(list);
for(int i = 0; i < list.length; i++)
System.out.print(list[i] + " ");
}

public static void mergeSort(int[] list) {
if(list.length > 1) {
// Merge sort first half
int[] firstHalf = new int[list.length / 2];
System.arraycopy(list, 0, firstHalf, 0, list.length / 2);
mergeSort(firstHalf);

// Merge sort second half
int secondHalfLength = list.length - list.length / 2;
int[] secondHalf = new int[secondHalfLength];
System.arraycopy(list, list.length / 2,
secondHalf, 0, secondHalfLength);
mergeSort(secondHalf);

// Merge firstHalf with secondHalf into list
merge(firstHalf, secondHalf, list);
}
}

// Merge two sorted lists
public static void merge(int[] list1, int[] list2, int[] temp) {
int current1 = 0; // Current index in list1
int current2 = 0; // Current index in list2
int current3 = 0; // Current index in temp

while (current1 < list1.length && current2 < list2.length) {
if(list1[current1] < list2[current2])
temp[current3++] = list1[current1++];
else
temp[current3++] = list2[current2++];
}

while (current1 < list1.length)
temp[current3++] = list1[current1++];

while (current2 < list2.length)
temp[current3++] = list2[current2++];
}
}


The algorithm above is fairly self explanatory. The merge method creates two new arrays, copies the two halves of the original and recursively breaks them apart into halves until that have length 1. Finally, the two lists are merged in the merge method into a temp array through a simple comparison.

Merge sort (esp. for larger arrays) is much more efficient than yesterdays insertion sort being theta(n log n) rather than exponential.