分类技术根据记录所处的环境不同而分为内部分类和外部分类两大类。内部分类是指分类期间全部数据都存放在内存的分类方法；外部分类则是针对大量记录而言的，分类期间，全部记录已不能同时存放在内存，需要记录在内、外存之间移动。归并分类是分治法中的一种算法，属于内部分类技术。若果用分治策略来设计分类算法，则可使最坏情况下时间变为O(nlogn)，这样的算法称为归并分类算法，也称为二路归并分类算法。

分治法的思想是将一个难以直接解决的问题分解成容易求解的子问题，以便各个击破、分而治之。利用分治法求解问题的过程是，将整个问题分解成若干子问题后分而治之；如果分解得到的子问题仍然不易求解，可反复使用分治策略将这些子问题分成更小的子问题，直至产生出容易求解的子问题，最后逐步合成这些子问题的解，以得到问题的解。归并分类就是分治法中的一种算法。

分类问题就是按照关键值的一种排序关系，如大于关系。如根据关键值的不增或不减次序，把文件中的各种记录一次排列起来，可使得一个无序文件变成有序文件。

（1）向量表示。要分类的初始文件的各个记录，按其自然顺序存放在连续一块内存空间中。

（2）链表表示。要分类文件的每个记录作为链表结构的一个结点，并按照各个记录的原始次序链接起来。

（3）地址向量。将要分类文件的各个记录存贮到内存的各块中，这些存贮块的地址是不连续的。按各记录的原始次序，将这些块的首地址依次存如内存的一块连续单元中，这样由各块的首地址组成一个向量，这个向量就是地址向量。

分类技术根据记录所处的环境不同而分为内部分类和外部分类两大类。内部分类是指分类期间全部数据都存放在内存的分类方法；外部分类则是针对大量记录而言的，分类期间，全部记录已不能同时存放在内存，需要记录在内、外存之间移动。常见的几种内部分类技术包括：

（1）计数分类。主要思想是对于每个记录，都要计算文件中其它记录的关键字值有多少是大于该记录的关键字值，从而找到这个记录的正确分类位置，这是一种效率较低的分类方法。

（2）选择分类。以教师对学生的考试成绩按分数进行分类为例，首先找到成绩最好的试卷，并把它出来，作为新一叠试卷的头一份试卷，然后在剩余的试卷中再选出分数最高的试卷，并把它放在新的那叠试卷之上，如此继续下去，最后就完成了按分数高低分类这些试卷，这个过程即为选择分类。

（3）冒泡分类。每一次仅进行相邻两个记录的比较，使位于文件底部的合适记录一下子放到文件的顶部，而只能每次向上移动一步，缓慢升到顶部，因此一个文件的全部分类是由多次重复比较相邻记录的关键字而实现的。

（4）线性插入；将原始文件顺序的第二个记录的关键字与第一个记录的关键字进行比较后，把第二个记录放到一个相对于第一个记录的合适位置。然后再取第三个记录于前二个记录进行比较关键字，并把第三个记录放到相对于前两个记录的合适位置，如此继续下去，最后完成分类。

（5）折半插入，它是线性插入的改进。

（6）归并分类，两个分类文件的归并问题和k个分类文件的归并问题。

设待分类的数据序列包含n个数据元素。

（1）先把该序列分成n个子序列，每个子序列只包含一个数据，显然，这n个子序列都是有序的；

（2）将这n个子序列两个一组，可分成（n+1）/2（取整）个互不相交的组；

（3）对每个组的2个子序列进行二路归并，总共得到（n+1）/2个有序子序列；

（4）对这些有序子序列两个一组，对每个组进行二路归并。

如此继续下去，最后得到一个有序的结果序列。

归并分类算法时间复杂度为O(nlogn)。归并分类方法相当充分地反映了使用分治策略对数据对象分类的长处，但是仍存在一些明显的不足，从而限制了分类效率的进一步提高。

首先，每当计划被分为只含有两个元素的子集合时，还需要使用二次递归调用将这子集合分成单个元素的集合。这表明该算法执行到将集合分成含元素相当少的子集合时，很多时候不是用在实际的分类，而是消耗在递归外了。

另外，归并算法使用了辅助数组，这是一个明显的不足之处，但是由于不可能在两个已分类集合的原来位置上进行适当的归并，所以这n个位置的附加空间对于本算法是必须的，不过，使用一个以整数表示的链表信息数组来代替辅助数组可以节省一些附加空间。

使用链接的归并分类模型，，其主要算法如下：

在这个算法中，利用辅助数组LINK[low:high]将全长数组A[low:high]按非降次序分类。LINK中值表示按分类次序给出A下标的表，并将p置于指示这表开始处。

使用链接表归并已分类的集合，其主要算法如下：