Demo: Merge-Sort

This article shows a simple demo about how the merge-sort works, which follows divide-and-conque.

BTW, Java is strickly passing by value.

For other type of array, the only thing you need to care is Claim of the type and the comparison of the objects in that type.

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * A Simple Demo for Merge-Sort.
 */

/**
 * @author antonio081014
 * @time: Sep 24, 2012, 8:52:26 AM
 */
public class A {

    public static void main(String[] args) throws Exception {
 A main = new A();
 main.run();
 System.exit(0);
    }

    public void run() throws Exception {
 int[] test = { 2, 1, 4, 6, 7, 3, 5, 0, 9 };
 System.out.println(Arrays.toString(test));
 mergesort(test, 0, test.length - 1);
 System.out.println(Arrays.toString(test));
    }

    public void mergesort(int[] array, int low, int high) {
 if (low < high) {
     int middle = (low + high) / 2;
     mergesort(array, low, middle);
     mergesort(array, middle + 1, high);
     merge(array, low, middle, high);
 }
    }

    public void merge(int[] array, int low, int middle, int high) {
 Queue<Integer> list1 = new LinkedList<Integer>();
 Queue<Integer> list2 = new LinkedList<Integer>();
 for (int i = low; i <= middle; i++)
     list1.add(array[i]);
 for (int i = middle + 1; i <= high; i++)
     list2.add(array[i]);
 int i = low;
 while (!list1.isEmpty() && !list2.isEmpty()) {
     if (list1.peek() <= list2.peek()) {
  array[i++] = list1.poll();
     } else {
  array[i++] = list2.poll();
     }
 }

 while (!list1.isEmpty())
     array[i++] = list1.poll();
 while (!list2.isEmpty())
     array[i++] = list2.poll();
    }
}