Code Pumpkin

Merge Sort | Sorting Algorithm

October 15, 2017
Posted by Pumpkin
Subscribe

Merge Sort is a Divide and Conquer algorithm. Divide and conquer algorithms divide the original data into smaller sets of data to solve the problem.

During the Mergesort process, the elements of the array or collections are divided into two parts. To split an array, Mergesort will take the middle element of the array and split the array into its left and its right part. The resulting sub arrays are again recursively divided into two sub parts until the size of the each subarray becomes 1.

Once the splitting process completes, merging process starts recursively which combines results of all the subarrays.

To combine both arrays, merging starts in each subarray at the beginning. It picks the smaller element and inserts this element into the beginning of the combined subarray. Then it compares the remaining elements of the two subarray and store them into combined sorted array. at the end of this, it produces combined sorted output array.

Merge Sort Average Case

Above GIF Images are generated through  Algorithms mobile app.


Algorithm

The logic for the merge sort is as follow:

  • Divide : The first step would be to divide the problem into two or more than two sub-problems. As already stated, the input is an array containing N elements, this algorithm divides the array into two sub-arrays containing half of element in each of them, i.e. N/2. So division step is straight forward; just find the mid element in the array and divide it.
  • The second step would be to solve these subproblems recursively until we reach to the base case where the solution is direct which is the subarray have only single elements which itself is sorted.
     
  • Conquer : The third step would be to combine the solution of individual sub-problems to formulate the overall solution to our problem.

The above three steps are also illustrated in above GIF image as well as below diagram:

 


In short, the algorithm for merge sort will be divided into two main parts

  1. Divide the input array into subarrays and after that
  2. Merge all the arrays to form the sorted array.

Java Program Implementation


public class MergeSortExample {

	public static void main(String[] args) {
		int[] inputArr = {4,1,7,5,3,2,6};
		MergeSort ms = new MergeSort(inputArr);
		
		
		System.out.println("------------------\n Input \n------------------");
		ms.display();
		ms.sort();
		
		System.out.println("\n\n------------------\n After mergeSort() \n------------------");
		ms.display();
	}

}

class MergeSort{
	int[] arr;
	
	MergeSort(int[] arr)
	{
		this.arr = arr;
	}
	
	/**
	 * Main mergeSort() function which will internally calls
	 * overloaded recursive mergeSort(left,right) function
	 */
	public void sort()
	{
		sort(0,arr.length-1);
	}
	
	/**
	 * Overloaded Recursive mergeSort() function
	 * 
	 * @param left	left index of the input array
	 * @param right	right index of the input array
	 */
	public void sort(int left,int right)
	{
		int middle;  // middle index of the input array
		if(left<right)
		{
			middle = (left+right)/2;
			sort(left,middle);   // to divide the array -  left Half
			sort(middle+1,right); // Right Half
			
			merge(left,middle,right); // to merge sorted left and right halves
		}
	}
	
	/**
	 * merge function which will be internally called from sort() method.
	 * 
	 * @param left 		left index of the input array
	 * @param middle 	middle index of the input array
	 * @param right 	right index of the input array
	 */
	public void merge(int left,int middle,int right)
	{
		int n1,n2;
		int[] leftArray, rightArray;
		n1 = middle-left+1;
		n2 = right-middle;
		
		// Temporary left and right array
		leftArray = new int[n1];
		rightArray = new int[n2];
		
		for(int i=0; i < n1; i++)
		{
			leftArray[i]=arr[left+i];
		}
		for(int j=0;j < n2;j++)
		{
			rightArray[j]=arr[middle+1+j];
		}
		
		int i=0, 	// pointer for the leftArray
			j=0, 	// pointer for the rightArray
			k=left;	// pointer for the main Array i.e. arr
		
		while(i < leftArray.length && j < rightArray.length)
		{
			if(leftArray[i] 

Time Complexity

From the algorithm we can see that it is a recursive algorithm and the time complexity for the same can be calculated as below: 

T(n) = 2T(n/2) + \Theta(n) which is resolved to O(n logn) time complexity.

Average Case

Merge Sort Average Case

Worst Case (Reverse List)

Merge Sort Worst Case

Above GIF Images are generated through  Algorithms mobile app.


Space Complexity

It is having O(n) space complexity.


Advantage

  • It is more efficient as it is in worst case also the runtime is O(nlogn)
  • It provides stable sorting.

Disadvantage

  • It is takes lots of space(O(n)) which may slower down operations for the last data sets in some cases.

Java and many other languages use merge sort as default technique for sorting objects.

That's all for this topic. If you guys have any suggestions or queries, feel free drop a comment. We would be happy to add that in our post. You can also contribute your articles by creating contributor account here

Happy Learning 🙂

You can also check the other articles on sorting and searching such as selection sortbinary searchfibonacci searchbubble sort etc.  You will also like to enhance your knowledge by going through our other articles on different algorithms and data structures.


Further Reading For interview Preparation

  1. Program To Find Unique Array Element
  2. Program To Check Whether A Number Is Prime Or Not
  3. Program To Check If A Given Number Is Power Of Two Or Not?
  4. Program To Find Number Of Set Bits In The Binary Number
  5. Sudoku Solver
  6. N Queen Problem
  7. Graph Search - Breadth First Search
  8. Graph Search - Depth First Search
  9. interface VS abstract class
  10. Access Modifiers (public, private, protected and default scope)
  11. HashMap vs Hashtable Vs SynchronizedMap Vs ConcurrentHashMap
  12. CountDownLatch Vs CyclicBarrier

Tags: , , ,


Comments and Queries

If you want someone to read your code, please put the code inside <pre><code> and </code></pre> tags. For example:
<pre><code class="java"> 
String foo = "bar";
</code></pre>
For more information on supported HTML tags in disqus comment, click here.

Total Post : 80
Subscribe
Contribute Your Articles

Interview Experiences

Related Books

Like Us On Facebook

Alexa Page Rank