Merge Sort

 

Overview

Merge sort is one of the most important sorting algorithms out there. It is classified as a O(n log n) comparison-based sorting algorithm, which utilizes a divide and conquer approach. With most implementations, merge sort produces a stable sort. It was originally conceived by John von Neumann in 1945.

Concept

The basic steps of Merge Sort include:

  1. Divide: Find the middle index of the initial list and divide the initial list in half.
  2. Conquer: Recursively sort the two lists created during the divide step.
  3. Merge: Merge the two sorted lists back into the main sorted list.

Algorithmic Complexity

Big-O

AlgorithmData StructureTime Complexity - BestTime Complexity - AverageTime Complexity - WorstWorst Case Auxiliary Space Complexity
Merge SortArrayO(n log(n))O(n log(n))O(n log(n))O(n)

Implementation

Java Implementation


import java.util.ArrayList;
import java.util.List;

/**
 * Merge Sort algorithm implementation
 * 
 * www.algorithmiccomplexity.com
 */
public class MergeSort {
	
	public static List mergeSort(List unsortedList)
	{
	   if (unsortedList.size() <= 1)
	   {
	      return unsortedList;
	   }

	   List left = new ArrayList<>();
	   List right = new ArrayList<>();

	   int middle = unsortedList.size() / 2;

	   for (int i = 0; i < middle; i++)
	   {
	      left.add(unsortedList.get(i));
	   }
	   for (int i = middle; i < unsortedList.size(); i++)
	   {
	      right.add(unsortedList.get(i));
	   }

	   left = mergeSort(left);
	   right = mergeSort(right);

	   return merge(left, right);
	}

	private static List merge(List left, List right)
	{
	   List result = new ArrayList<>();

	   while (left.size() > 0 || right.size() > 0)
	   {
	      if (!left.isEmpty() && !right.isEmpty())
	      {
	         if (left.get(0) <= right.get(0))
	         {
	            result.add(left.remove(0));
	         }
	         else
	         {
	            result.add(right.remove(0));
	         }
	      }
	      else if (!left.isEmpty())
	      {
	         result.add(left.remove(0));
	      }
	      else if (!right.isEmpty())
	      {
	         result.add(right.remove(0));
	      }
	   }

	   return result;
	}
	
	/**
	 * Test driver for the merge sort algorithm.
	 * 
	 * @param args Command line arguments {@code null}.
	 */
	public static void main(String[] args)
	{
		List unsortedList = new ArrayList<>();
		unsortedList.add(10);
		unsortedList.add(5);
		unsortedList.add(3);
		unsortedList.add(7);
		unsortedList.add(1);
		unsortedList.add(8);
		unsortedList.add(8);
		unsortedList.add(0);
		unsortedList.add(6);
		
		System.out.println(unsortedList);
		unsortedList = MergeSort.mergeSort(unsortedList);
		System.out.println(unsortedList);
	}
}

References

Wikipedia: Merge sort

Test Your Knowledge – Click Here!

<- back