[算法入门]归并排序非递归实现，大家一起来找茬啊～

原理

归并排序的原理大家可以先看看百度百科：
http://baike.baidu.com/link?url=f08CeKe1xv877bTlLsWRBY3WHsHEjUvHvch6EEqz3LM_RqECZnF4BQtx9mACl2GJAaHWHVSoIBpV3DLVZ542pFE5M7fFfVCPo276sZsgdQJRP3jao_QlSW-egCiqn_YH
放一幅图在这里，便于理解：

思路

归并排序主要是要先分解数组，排序，然后再合并数组。

分解

通过归并排序的原理，我们可以知道：
1、最小的分组单位是2个数字为一组，然后是4个数字，8个数字等等等。（这里我们用步长来代称每组数字个数）
2、若分组后剩下的数字个数比步长小，没有关系，我们还是把他们算成一个组来进行归并。

排序

排序是在两个相邻组别中进行排序。

1、排序的时候，先将两个相邻组别中最小的几个数字挑出来，放到一个临时数组中。
2、若第一个组别中的数字没有被挑完，则将它们依次放入临时数组。
3、若第二个组别中的数字没有被挑完，将它们依次放入临时数组中。

合并

1、把临时数组中的数字再copy回原数组即可。

实现

看看代码：

    /*** Merge sort without recursion* @param result* @return*/public int[] mergeSort_not_recursion(int[] result) {int length = result.length;int[] temp = new int[length]; // To store the minus numbersif (result.length == 0) {LogUtils.e("mergeSort_not_recursion", "The count of array is null", null);return -1;}// Step one: Split array [分解]// Split arrayint gap, i = 0;for (gap = 1; gap < length; gap *= 2) {// To use gap splits numbersfor (i = 0; i + 2 * gap - 1 < length; i = i + 2 * gap) {mergesort(temp, i, i + gap, i + 2 * gap - 1, result);}// The rest of numbers to mergesortif (i + gap < length) {mergesort(temp, i, i + gap, length - 1, result);}}return result;}public int[] mergesort(int[] temp, int min, int middle, int high, int[] result){int index = 0;int i = min;int j = middle;// Step two：Sort [排序]// Get The smaller numbers,// Store them in tempwhile(i <= middle-1 && j<=high) {if (result[i] >= result[j]) {temp[index] = result[j];j++;index++;}else{temp[index] = result[i];i++;index++;}}// To store the rest of numbers to tempwhile (i < middle) {temp[index] = result[i];i++;index++;}// To store the rest of numbers to tempwhile (j < high) {temp[index] = result[j];j++;index++;}// Step Three：Merge [归并]// To copy numbers back to resultint k = 0;while (k < index) {result[min] = temp[k];k++;min++;}return result;}
}