# 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++)
{
}
for (int i = middle; i < unsortedList.size(); 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))
{
}
else
{
}
}
else if (!left.isEmpty())
{
}
else if (!right.isEmpty())
{
}
}

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<>();

System.out.println(unsortedList);
unsortedList = MergeSort.mergeSort(unsortedList);
System.out.println(unsortedList);
}
}

``````

## References

Wikipedia: Merge sort