合并排序是最有效的排序算法之一。
它基于将一个列表分解为几个子列表，直到每个子列表由一个元素组成，然后将这些子列表合并为一个排序列表的思想，根据分而治之原理工作。

合并排序工作规则

分而治之的概念涉及三个步骤：

• 将问题分为多个子问题。

• 解决子问题。
  想法是将问题分解为原子子问题，并其中实际解决。

• 结合子问题的解决方案以找到实际问题的解决方案。

因此，合并排序工作规则涉及以下步骤：

• 将未排序的数组划分为子数组，每个子数组包含一个元素。

• 取相邻的两个单元素数组对，并将它们合并以形成2个元素的数组。

• 重复该过程，直到获得单个排序的数组。

大小为'N'的数组分为两个部分，每个大小均为'N/2'。
然后将这些数组进一步划分，直到达到单个元素。

这里的基本情况是达到一个要素。
当遇到基本情况时，我们开始合并左部分和右部分，最后得到一个排序的数组。

合并排序反复将一个数组分解为几个子数组，直到每个子数组由单个元素组成，然后以导致排序数组的方式合并这些子数组。

合并排序算法流程

数组= {70,50,30,10,20,40,60}

合并排序

我们反复将数组分为两部分，左部分和右部分。
划分从中间元素开始。

我们进行划分，直到达到单个元素，然后开始将它们组合以形成有序数组。

合并排序实现

我们将在Java，C和Python中实现合并排序算法。

1. Java实现

package com.theitroad.ds;

public class MergeSort {

	public static void main(String[] args) {

		int[] arr = { 70, 50, 30, 10, 20, 40, 60 };

		int[] merged = mergeSort(arr, 0, arr.length - 1);

		for (int val : merged) {
			System.out.print(val + " ");
		}

	}

	public static int[] mergeTwoSortedArrays(int[] one, int[] two) {

		int[] sorted = new int[one.length + two.length];

		int i = 0;
		int j = 0;
		int k = 0;

		while (i < one.length && j < two.length) {

			if (one[i] < two[j]) {
				sorted[k] = one[i];
				k++;
				i++;
			} else {
				sorted[k] = two[j];
				k++;
				j++;
			}
		}

		if (i == one.length) {

			while (j < two.length) {
				sorted[k] = two[j];
				k++;
				j++;
			}
		}

		if (j == two.length) {

			while (i < one.length) {
				sorted[k] = one[i];
				k++;
				i++;
			}
		}

		return sorted;

	}

	public static int[] mergeSort(int[] arr, int lo, int hi) {

		if (lo == hi) {
			int[] br = new int[1];
			br[0] = arr[lo];

			return br;
		}

		int mid = (lo + hi)/2;

		int[] fh = mergeSort(arr, lo, mid);
		int[] sh = mergeSort(arr, mid + 1, hi);

		int[] merged = mergeTwoSortedArrays(fh, sh);

		return merged;
	}

}

输出值

合并排序算法Java实现

2. C实现

#include <stdio.h>

void merge(int arr[], int l, int m, int r) 
{ 
  int i, j, k; 
  int n1 = m - l + 1; 
  int n2 =  r - m; 

  /* create temp arrays */
  int L[n1], R[n2]; 

  /* Copy data to temp arrays L[] and R[] */
  for (i = 0; i < n1; i++) 
      L[i] = arr[l + i]; 
  for (j = 0; j < n2; j++) 
      R[j] = arr[m + 1+ j]; 

  /* Merge the temp arrays back into arr[l..r]*/
  i = 0; //Initial index of first subarray 
  j = 0; //Initial index of second subarray 
  k = l; //Initial index of merged subarray 
  while (i < n1 && j < n2) 
  { 
      if (L[i] <= R[j]) 
      { 
          arr[k] = L[i]; 
          i++; 
      } 
      else
      { 
          arr[k] = R[j]; 
          j++; 
      } 
      k++; 
  } 

  /* Copy the remaining elements of L[], if there 
     are any */
  while (i < n1) 
  { 
      arr[k] = L[i]; 
      i++; 
      k++; 
  } 

  /* Copy the remaining elements of R[], if there 
     are any */
  while (j < n2) 
  { 
      arr[k] = R[j]; 
      j++; 
      k++; 
  } 
} 

/* l is for left index and r is the right index of the 
 sub-array of arr to be sorted */
void mergeSort(int arr[], int l, int r) 
{ 
  if (l < r) 
  { 
      //Same as (l+r)/2, but avoids overflow for 
      //large l and h 
      int m = l+(r-l)/2; 

      //Sort first and second halves 
      mergeSort(arr, l, m); 
      mergeSort(arr, m+1, r); 

      merge(arr, l, m, r); 
  } 
} 

void printArray(int A[], int size) 
{ 
  int i; 
  for (i=0; i < size; i++) 
      printf("%d ", A[i]); 
  printf("\n"); 
} 

/* Driver program to test above functions */
int main() 
{ 
  int arr[] = {70, 50, 30, 10, 20, 40,60}; 
  int arr_size = sizeof(arr)/sizeof(arr[0]); 

  printf("Given array is \n"); 
  printArray(arr, arr_size); 

  mergeSort(arr, 0, arr_size - 1); 

  printf("\nSorted array is \n"); 
  printArray(arr, arr_size); 
  return 0; 
}

输出值

合并Sort C实现

3. Python实现

def merge_sort(unsorted_array):
  if len(unsorted_array) > 1:
      mid = len(unsorted_array) //2  # Finding the mid of the array
      left = unsorted_array[:mid]  # Dividing the array elements
      right = unsorted_array[mid:]  # into 2 halves

      merge_sort(left)
      merge_sort(right)

      i = j = k = 0

      #  data to temp arrays L[] and R[]
      while i < len(left) and j < len(right):
          if left[i] < right[j]:
              unsorted_array[k] = left[i]
              i += 1
          else:
              unsorted_array[k] = right[j]
              j += 1
          k += 1

      # Checking if any element was left
      while i < len(left):
          unsorted_array[k] = left[i]
          i += 1
          k += 1

      while j < len(right):
          unsorted_array[k] = right[j]
          j += 1
          k += 1

# Code to print the list
def print_list(array1):
  for i in range(len(array1)):
      print(array1[i], end=" ")
  print()

# driver code to test the above code
if __name__ == &#039;__main__&#039;:
  array = [12, 11, 13, 5, 6, 7]
  print("Given array is", end="\n")
  print_list(array)
  merge_sort(array)
  print("Sorted array is: ", end="\n")
  print_list(array)

输出值

合并排序Python代码

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

1.空间复杂性

辅助空间：O(n)就地排序：否算法：分而治之

2.时间复杂度

合并排序是一种递归算法，时间复杂度可以表示为以下递归关系。

T(n)= 2T(n/2)+ O(n)

上述重复的解决方案是O(nLogn)。
大小为N的列表分为最大的Logn部分，并且将所有子列表合并为一个列表需要O(N)时间，该算法的最坏运行时间是O(nLogn)

最佳情况下的时间复杂度：O(n * log n)

最坏情况下的时间复杂度：O(n * log n)

平均时间复杂度：O(n * log n)

在3种情况下(最差，平均和最佳)，MergeSort的时间复杂度为O(n * Log n)，因为mergesort总是将数组分为两半，并花费线性时间来合并两半。