归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。递归形式的算法在形式上较简洁，但实用性很差。一般情况下，很少利用二路归并排序法进行内部排序。
概述
归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
归并排序采用的是递归来实现，属于“分而治之”，将目标数组从中间一分为二，之后分别对这两个数组进行排序，排序完毕之后再将排好序的两个数组“归并”到一起，归并排序最重要的也就是这个“归并”的过程，归并的过程中需要额外的跟需要归并的两个数组长度一致的空间。
效果图：
步骤
申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
设定两个指针，最初位置分别为两个已经排序序列的起始位置
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤3直到某一指针达到序列尾
将另一序列剩下的所有元素直接复制到合并序列尾
实例
原始数据：
3 5 2 6 2
归并的前提是将数组分开，一分为二，再一分为二，分到不能再分，进行归并。
第一轮分隔，索引2 ((0+4)/2=2) 为中间
[3 5 2] [6 2]
第二轮分隔，对[3 5 2]进行分隔
[3 5] [2] [6 2]
第三轮分隔，对[3 5]进行分隔
[3] [5] [2] [6 2]
合并[3] [5]
[3 5] [2] [6 2]
合并[3 5] [2]
[2 3 5] [6 2]
第四轮分隔，对[6 2]进行分隔
[2 3 5] [6] [2]
合并[6] [2]
[2 3 5] [2 6]
合并[2 3 5] [2 6]
[2 2 3 5 6]
代码实现(Java)
package com.coder4j.main.arithmetic.sorting; public class Merge { private static int mark = 0; /** * 归并排序 * * @param array * @param low * @param high * @return */ private static int[] sort(int[] array, int low, int high) { int mid = (low + high) / 2; if (low 测试输出结果：
正在进行第1次分隔，得到 [0-2] [3-4] 正在进行第2次分隔，得到 [0-1] [2-2] 正在进行第3次分隔，得到 [0-0] [1-1] 合并:[0-0] 和 [1-1] 合并:[0-1] 和 [2-2] 正在进行第4次分隔，得到 [3-3] [4-4] 合并:[3-3] 和 [4-4] 合并:[0-2] 和 [3-4] 最终结果 2 2 3 5 6
经测试，与实例中结果一致。
以上就是归并排序的原理及java代码实现的详细内容，更多请关注0133技术站其它相关文章！
