归并排序是利用递归和分而治之的技术将数据序列划分成为越来越小的半子表，再对半子表排序，最后再用递归步骤将排好序的半子表合并成为越来越大的有序序列，归并排序包括两个步骤，分别为：

      1）划分子表

      2）合并半子表 

     首先我们来讨论归并算法，归并算法将一系列数据放到一个向量中，索引范围为[first,last],这个序列由两个排好序的子表构成，以索引中点（mid）为分界线，以下面一个序列为例

    7，10，19，25，12，17，21，30，48

   这样的一个序列中，分为两个子序列 7,10,19,25  和 12,17,21,30,48，如下图所示：

再使用归并算法的时候的步骤如下：

 第一步：比较v[indexA]=7和v[indexB]=12,将较小的v[indexA]取出来放到临时向量tempArray中，然后indexA加1 

 第二步：比较v[indexA]=10和v[indexB]=12,将较小的10放到临时变量tempArray中，然后indexA++;

第三步：比较v[indexA]=19与v[indexB]=12，将较小的12存放到临时变量tempArray中，然后indexB++;

第四步到第七步：按照以上规则，进行比对和存储，得到如下结果：

最后一步：将子表b中剩余项添加到临时向量tempArray中 

然后将临时变量中的值按照索引位置，拷贝回向量v中，就完成了对向量v的归并排序

java代码实现：

所有函数共用一个临时数组temp，每次都new一个临时数组开销太大

package org.conan.myhadoop.mr;

import java.util.Arrays;

    public class MergeSort {  
      
        public static int[] sort(int[] array, int low, int high,int[] temp) {  
            
            int mid = (low + high) / 2;  
            if (low < high) {  
                // 左边  
                sort(array, low, mid,temp);  
                // 右边  
                sort(array, mid + 1, high,temp);  
                // 左右归并  
                merge(array, low, mid, high,temp);  
            }  
            return array;  
        }  
      
        public static void merge(int[] array, int first, int mid, int last,int[] temp) {  
        
            int i = first, j = mid + 1;  
            int m = mid,   n = last;  
            int k = 0;  
            // 把较小的数先移到新数组中  
            while (i <= m && j <= n)  
            {  
                if (array[i] <= array[j])  
                    temp[k++] = array[i++];  
                else  
                    temp[k++] = array[j++];  
            }  
            // 把左边剩余的数移入数组   
            while (i <= m)  
                temp[k++] = array[i++];  
            // 把右边边剩余的数移入数组    
            while (j <= n)  
                temp[k++] = array[j++];  
             // 把临时数组中的数覆盖array数组      
            for (i = 0; i < k; i++)  
                array[first + i] = temp[i];  
        }  
      
          
        // 归并排序的实现  
        public static void main(String[] args) {  
      
            int[] array = { 2, 7, 8, 3, 1, 6, 9, 0, 5, 4 };  
            int[] temp=new int[array.length];
            MergeSort.sort(array, 0, array.length-1,temp);  
            System.out.println(Arrays.toString(array));  
        }  
    }

参考文章：

http://www.cnblogs.com/jillzhang/archive/2007/09/16/894936.html

http://blog.csdn.net/morewindows/article/details/6678165/

 

本文出自 “点滴积累” 博客，请务必保留此出处http://tianxingzhe.blog.51cto.com/3390077/1698530