本教程显示了如何用Java编写合并排序程序。合并排序被称为"分而治之算法"，它被认为比简单的排序算法(例如选择排序和插入排序)更有效。

合并排序算法

合并排序的算法基于合并过程，其中将两个已排序的数组合并为一个大的已排序数组。要首先合并较小的数组，我们确实需要将数组也分成较小的数组，这样有效地进行合并排序是一个两步过程。

• 将输入数组分为两半，此过程将递归执行，直到获得只有一个元素的子数组，这是递归除法的基本情况。这些一个元素的子数组每个都被视为排序数组。
• 在此步骤中，将对这些较小的数组进行排序和递归合并，直到再次获得较大的排序数组为止。合并过程从底部开始，在该处对一对单个元素子数组进行排序并合并以创建两个元素的数组。然后，将一对这样的两个元素的排序子数组合并以创建四个元素的排序数组，依此类推。

合并排序Java程序

public class MergeSort {
  public static void main(String[] args) {
    int[] arr = {43, 39, 54, 61, 81, 55, 92, 7, 0, 15, 112, 10};
    System.out.println("Original array- " + Arrays.toString(arr));
    MergeSort ms = new MergeSort();
    ms.mergeSortRecursive(arr, 0, arr.length-1);
    System.out.println("Sorted array after merge sorting- " + Arrays.toString(arr));
  }
	
  private void mergeSortRecursive(int[] arr, int start, int end){
    //base case
    if (start == end){
        return;
    }else{
      // Middle point of the array
      int middle = (start + end)/2;  
      // divide array into two parts using middle point
      mergeSortRecursive(arr, start, middle);        
      mergeSortRecursive(arr, middle+1, end);
      // call merge process
      merge(arr, start, middle, end);
    }
  }
    
  private void merge(int[] arr, int start, int middle, int end){
    // Create two temp arrays for two halves
    int temArray1Length = middle - start + 1;
    int temArray2Length = end - middle;
    int[] temp1 = new int[temArray1Length];
    int[] temp2 = new int[temArray2Length];
    for(int i = 0; i < temArray1Length; i++){
      temp1[i] = arr[start + i];
    }
    for(int j = 0; j < temArray2Length; j++){
      temp2[j] = arr[middle + 1 + j];
    }

    int i =0;        
    int j = 0;
    // merging process, merge two temp arrays put the 
    // sorted elements in original array 
    while((i < temArray1Length) && (j < temArray2Length)){
      if(temp1[i] < temp2[j]){
        arr[start] = temp1[i++];
      }else{
        arr[start] = temp2[j++];
      }
      start++;
    }
    // Add left over elements from temp arrays
    while(i < temArray1Length){
      arr[start++] = temp1[i++];
    }
    while(j < temArray2Length){
      arr[start++] = temp2[j++];
    }
  }
}

输出：

Original array- [43, 39, 54, 61, 81, 55, 92, 7, 0, 15, 112, 10]
Sorted array after merge sorting- [0, 7, 10, 15, 39, 43, 54, 55, 61, 81, 92, 112]

合并排序时间和空间复杂性

合并排序的时间复杂度为O(n * logn)，其中logn是细分数组的复杂度，n是在每个级别合并n个元素的复杂度。

合并排序的空间复杂度为O(n)，因为临时数组需要额外的空间，该空间等于输入数组的长度。