• 代码如下：

  

  创新互联建站是一家专业提供罗城企业网站建设,专注与成都网站设计、网站建设、外贸网站建设、H5开发、小程序制作等业务。10年已为罗城众多企业、政府机构等服务。创新互联专业网络公司优惠进行中。

  private void merge(int[] array, int left, int mid, int right) {
         int i = left;
         int j = mid;
         int length = right - left;
         int[] extra = new int[length];
         int k = 0;
  
         while(i < mid && j < right) {
             if(array[i] <= array[j]) {
                 extra[k++] = array[i++];
             } else {
                 extra[k++] = array[j++];
             }
         }
  
         while (i < mid) {
             extra[k++] = array[i++];
         }
         while (j < right) {
             extra[k++] = array[j++];
         }
  
         // 从 extra 搬移回 array
         for (int t = 0; t < length; t++) {
         // 需要搬移回原位置，从 low 开始
             array[left + t] = extra[t];
         }
     }

• 递归实现操作：

  public void mergeSort(int[] array) {
     mergeSortInternal(array, 0, array.length);
  }
  
  private void mergeSortInternal(int[] array, int left, int right) {
     if(left >= right - 1)
       return;
  
     int mid = (left + right) >>> 1;
     mergeSortInternal(array, left, mid);
     mergeSortInternal(array, mid, right);
  
     merge(array, left, mid, right);
  }

• 非递归实现操作

  public void mergeSort(int[] array) {
         for (int i = 1; i < array.length; i = i * 2) {
             for (int j = 0; j < array.length; j = j + 2 * i) {
                 int low = j;
                 int mid = j + i;
                 if (mid >= array.length) {
                     continue;
                 }
                 int high = mid + i;
                 if (high > array.length) {
                     high = array.length;
                 }
                 merge(array, low, mid, high);
             }
         }
     }

性能分析

• 时间复杂度：O(N * log(N))
• 空间复杂度：O(N)
• 稳定性：稳定

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。

文章题目：java递归和非递归的实现-创新互联
标题链接：http://cdweb.net/article/doioch.html