# Merge Sort

### Merge Sort Merging

Merge Sort is a divide and conquer algorithm. It consists of two parts:

``````1) splitting the original list into smaller sorted lists recursively until there is only 1 element in the list,
2) merging back the presorted 1-element lists into 2-element lists, 4-element lists, and so on recursively.
``````

The merging portion is iterative and takes 2 sublists. The first element of the left sublist is compared to the first element of the right sublist. If it is smaller, it is added to a new sorted list, and removed from the left sublist. If it is bigger, the first element of the right sublist is added instead to the sorted list and then removed from the right sublist. This is repeated until either the left or right sublist is empty. The remaining non-empty sublist is appended to the sorted list. ### Big-O Runtime for Merge Sort

The Merge Sort algorithm is divided into two parts. The first part repeatedly splits the input list into smaller lists to eventually produce single-element lists. The best, worst and average runtime for this part is Θ(log N). The second part repeatedly merges and sorts the single-element lists to twice its size until the original input size is achieved. The best, worst and average runtime for this part is Θ(N). Therefore, the combined runtime is Θ(N log N).

### Merge Sort Input And Output In Java

In Java, a Merge Sort function can accept an array of numbers, sorts the numbers, and returns the sorted array.

`public static void main (String[] args) {	// sort() called below.   int[] inputArr = {3, 5, 2, 90, 4, 7};  MergeSort sorter = new MergeSort();  System.out.println(Arrays.toString(sorter.sort(inputArr)));  // This will print [2, 3, 4, 5, 7, 90]}`

### Divide and Conquer in Java

In Java, a Merge Sort algorithm is implemented with two functions: - `sort()` – responsible for recursively splitting the input array until each number is in its own array - `merge()` – responsible for merging two arrays in ascending order.

The example code block shows the `sort()` function. Notice the `sort()` function calls the `merge()` function on the result of the sorted left half of the list and the sorted right half of the list.

`public int[] sort(int[] arr) {  int length = arr.length;  if (length <= 1) {      return arr;  }  int mid = Math.floorDiv(length, 2);  int[] leftArray = Arrays.copyOfRange(arr, 0, mid);  int[] rightArray = Arrays.copyOfRange(arr, mid, length);  return merge(sort(leftArray), sort(rightArray));}`

### Merge Sort Merging

Merge Sort is a divide and conquer algorithm. The second part involves merging back the presorted 1-element lists into 2-element lists, 4-element lists, and so on recursively. The merging portion is iterative and takes 2 sublists. The first element of the left sublist is compared to the first element of the right sublist. If it is smaller, it is added to a new sorted list. If it is bigger, the first element of the right sublist is added instead to the sorted list. This is repeated until either the left or right sublist is empty. The remaining non-empty sublist is appended to the sorted list. 