# Merge Sortby Isai Damier, Android Engineer @ Google

```/*****************************************************************************
* Author: Isai Damier
* Title: Mergesort
* Project: geekviewpoint
* Package: algorithm.sorting
*
* Statement:
*   Given a disordered list of integers (or any other items),
*   rearrange the integers in natural order.
*
* Sample Input: {8,5,3,1,9,6,0,7,4,2,5}
*
* Sample Output: {0,1,2,3,4,5,5,6,7,8,9}
*
* Time Complexity of Solution:
*   Best = Average = Worst = O(n*log(n)).
*
* Approach:
*   Merge sort is a divide and conquer algorithm. In the divide and conquer
*   paradigm, a problem is broken into pieces where each piece still retains
*   all the properties of the larger problem -- except its size. To solve
*   the original problem, each piece is solved individually; then the pieces
*   are merged back together.
*
*   For illustration, imagine needing to sort an array of 200 elements using
*   selection sort. Since selection sort takes O(n^2), it would take about
*   40,000 time units to sort the array. Now imagine splitting the array
*   into ten equal pieces and sorting each piece individually still using
*   selection sort. Now it would take 400 time units to sort each piece;
*   for a grand total of 10*400 = 4000. Once each piece is sorted, merging
*   them back together would take about 200 time units; for a grand total of
*   200+4000 = 4,200. Clearly 4,200 is an impressive improvement over
*   40,000. Now imagine greater. Imagine splitting the original array into
*   groups of two and then sorting them. In the end, it would take about
*   1,000 time units to sort the array. That's how merge sort works.
****************************************************************************/
private void mergesort(int[] input, int first, int last) {
// break problem into smaller structurally identical pieces
int mid = (first + last) / 2;
if (first < last) {
mergesort(input, first, mid);
mergesort(input, mid + 1, last);
}
// merge solved pieces to get solution to original problem
int a = 0, f = first, l = mid + 1;
int[] tmp = new int[last - first + 1];

while (f <= mid && l <= last) {
tmp[a++] = input[f] < input[l] ? input[f++] : input[l++];
}
while (f <= mid) {
tmp[a++] = input[f++];
}
while (l <= last) {
tmp[a++] = input[l++];
}
a = 0;
while (first <= last) {
input[first++] = tmp[a++];
}
}```
```import org.junit.Test;
import static org.junit.Assert.*;

public class SortingTest {

@Test
public void testMergesort() {
System.out.println(""mergesort"");
int[] input = {8, 5, 3, 1, 9, 6, 0, 7, 4, 2, 5};
Sorting instance = new Sorting();
instance.mergesort(input);
for (int i = 1; i < input.length; i++) {
if (input[i - 1] > input[i]) {
fail(""mergesort method fails."");
}
}
}
}```