Merge sort algorithm is one of the fastest sorting algorithms. It is more complicated to understand for some people but once you get it, you are the boss of sorting. It is uses recursion compare to other iterative sorting methods such as bubble and insertion sorting. The logic is this: divide an array into two parts, keep recursively dividing each created new part into two more parts until part will contain only one element. After that recursively make calls that will compare 2 parts, swap the elements if required, and merge the two parts. Continue until all the parts are completely merged into one sorted array. Take a look at the picture taken from wiki, to give you an idea.

Java code snippet

public static int[] insertionSort(int[] array) {
	for(int i = 1; i < array.length; i++) {	//start with second element	 		for(int j = i - 1; j >= 0 && array[j] > array[j + 1]; --j) { //compare to previous element and continue swapping till the start
			swap(array, j, j + 1);
		}
	}
	return array;
}
public static void swap (int[] array, int i, int j)
{
    int temp = array[i];
    array[i] = array[j];
    array[j] = temp;
}

Complexity analysis

Best: O(n log(n))

Worst: O(n log(n))

Dima Svirid

Software architect, JAVA, Spring, Hibernate, AngularJs, Backbone, MongoDB, Oracle. CTO and Co-Founder of Homeadnet.com

More Posts

Follow Me:

Tagged with: