#
Merge Sort

/***************************************************************************** * 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.""); } } } }