归并排序是一种高效的、基于分治法的排序算法，其时间复杂度为O(nlogn)，空间复杂度为O(n)

本文链接：https://blog.csdn.net/blog_programb/article/details/145379138

归并排序是一种高效的、基于分治法的排序算法，其时间复杂度为O(nlogn)，空间复杂度为O(n)。以下是关于归并排序的介绍：

基本思想：将原始数组A[0:n-1]中的元素分成两个大小大致相同的子数组：A[0:n/2]和A[n/2+1:n-1]，分别对这两个子数组单独排序，然后将已排序的两个数组归并成一个含有n个元素的有序数组。这个过程不断地进行二分，直至待排序数组中只剩下一个元素为止，然后不断合并两个排好序的数组段。
实现步骤
- 分割数组：将待排序的数组分成两个子数组，通常是平均分割。这一步持续递归，直到每个子数组只包含一个元素。
- 递归排序：递归地对左子数组和右子数组进行排序，直到它们都变成有序数组。
- 合并数组：将已排序的左子数组和右子数组合并成一个有序数组。合并的过程中，逐个比较左右两个数组的元素，并将较小的元素添加到结果数组中，直到两个数组都为空。
代码示例：以下是一个使用Java语言实现的归并排序的示例代码。

import java.util.Arrays;

public class MergeSort {
    public static void mergeSort(int[] arr, int start, int end) {
        if (start >= end) {
            return;
        }
        int mid = start + ((end - start) >> 1);
        mergeSort(arr, start, mid);
        mergeSort(arr, mid + 1, end);
        merge(arr, start, mid, end);
    }

    public static void merge(int[] arr, int start, int mid, int end) {
        int[] temp = new int[end - start + 1];
        int p1 = start;
        int p2 = mid + 1;
        int p = 0;
        while (p1 <= mid && p2 <= end) {
            if (arr[p1] > arr[p2]) {
                temp[p++] = arr[p2++];
            } else {
                temp[p++] = arr[p1++];
            }
        }
        while (p1 <= mid) {
            temp[p++] = arr[p1++];
        }
        while (p2 <= end) {
            temp[p++] = arr[p2++];
        }
        for (int i = 0; i < temp.length; i++) {
            arr[i + start] = temp[i];
        }
    }

    public static void main(String[] args) {
        int[] a = {2, 4, 6, 1, 3, 7, 9, 8, 5};
        mergeSort(a, 0, a.length - 1);
        System.out.println(Arrays.toString(a));
    }
}

优缺点
- 优点：归并排序是一种稳定的排序算法，即相等的元素在排序后保持原有顺序。此外，归并排序的时间复杂度始终为O(nlogn)，与输入序列的原始状态无关，因此适合于大型数据集的排序。
- 缺点：归并排序需要额外的存储空间来存放临时数组，因此空间复杂度较高，为O(n)。此外，归并排序的实现相对复杂，需要考虑如何高效地进行数组的分割和合并。

综上所述，归并排序是一种高效且稳定的排序算法，适用于大型数据集的排序。然而，由于其空间复杂度较高，因此在实际应用中需要根据具体需求进行权衡。
归并排序是一种基于归并操作的有效排序算法，属于分治法应用实例之一。主要过程包括将待排序列分解为更小的子序列直至单元素，随后逐步合并这些有序子序列以形成完整的有序列表。

此算法可借由递归来实施，在分阶段通过不断对半分割原始数组直到各部分仅含单一元素为止，递归深度大约等于 log₂n 。而在合阶段，则需将两个已排好序的小数组按顺序整合成一个新的大数组。

具体来说，归并排序执行时会经历以下几个关键环节：

数组分裂

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left_half = merge_sort(arr[:mid])
    right_half = merge_sort(arr[mid:])
    
    return merge_two_sorted_arrays(left_half, right_half)

排序与组合

def merge_two_sorted_arrays(sorted_arr1, sorted_arr2):
    index1, index2 = 0, 0
    merged_array = []

    while index1 < len(sorted_arr1) and index2 < len(sorted_arr2):
        if sorted_arr1[index1] < sorted_arr2[index2]:
            merged_array.append(sorted_arr1[index1])
            index1 += 1
        else:
            merged_array.append(sorted_arr2[index2])
            index2 += 1
    
    # Append any remaining elements from either array
    merged_array.extend(sorted_arr1[index1:])
    merged_array.extend(sorted_arr2[index2:])

    return merged_array

归并排序的时间复杂度在各种情况下保持一致，具体如下：

总体时间复杂度表达式可以通过各部分操作得出:
```
T(n) = 2T(n/2) + O(n)
```
使用主定理（Master Theorem）对上述递归方程求解得到结果为 O(n log n)，适用于最坏情况、最佳情况以及平均情况下的时间复杂度评估.

因此，无论是哪种情形下，归并排序都能保证拥有O(n log n) 的高效性能。

归并排序的空间复杂度是O(n)。

这是因为：

每次合并操作确实需要申请额外的内存空间，但这部分临时开辟的内存会在合并完成后立即被释放掉；
在任意时刻，只有一个函数在执行，因此也只会有一个临时的内存空间正在使用；
最大情况下，这个临时内存空间不会超过n个数据大小（即与输入数组同样大小），这就是为什么整体来说，归并排序所需辅助存储量为线性关系，也就是O(n)级别。

归并排序可以通过不同方式优化以减少额外空间需求：

使用自底向上的归并排序
这种方法不需要递归来分割数组，而是从单个元素开始逐步合并较小的已排序片段。这种方法避免了深度递归栈所占用的空间。

def bottom_up_merge_sort(arr):
    width = 1
    n = len(arr)
    while width < n:
        for i in range(0, n, width * 2):
            left = arr[i:i + width]
            right = arr[i + width:min(i + 2 * width, n)]
            arr[i:i + min(width * 2, n - i)] = merge(left, right)
        width *= 2

def merge(left, right):
    result = []
    while left and right:
        if left[0] <= right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    if left:
        result += left
    if right:
        result += right
    return result

利用自然归并排序降低空间消耗
此技术识别输入数据中已经存在的有序子序列（即"自然运行"），并将它们直接用于归并过程，减少了创建新分区时对辅助存储的需求。

自底向上归并排序与传统递归版归并排序的主要区别在于实现方式和性能特点：

实现方式：

传统归并排序依赖于递归来分割数组直到每个部分只含有单个元素，然后再逐步合并这些小的部分形成完整的有序序列。

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        L = arr[:mid]
        R = arr[mid:]

        merge_sort(L)
        merge_sort(R)

        i = j = k = 0

        while i < len(L) and j < len(R):
            if L[i] < R[j]:
                arr[k] = L[i]
                i += 1
            else:
                arr[k] = R[j]
                j += 1
            k += 1

        while i < len(L):
            arr[k] = L[i]
            i += 1
            k += 1

        while j < len(R):
            arr[k] = R[j]
            j += 1
            k += 1

自底向上归并排序则不采用递归的方式。相反，该方法直接从最小单元开始（通常是单一元素），然后逐渐增加待合并区间的大小，最终完成整个数组的排序过程。这种方式避免了因深度递归可能导致栈溢出的风险，并减少了函数调用所带来的额外开销。

def bottom_up_merge_sort(arr):
    width = 1
    n = len(arr)
    while width < n:
        for start in range(0, n, width * 2):
            left_start = start
            right_end = min(start + width * 2, n)
            midpoint = min(left_start + width, right_end)

            # Perform the merge operation on subarrays defined by indices.
            merged = []
            left_index, right_index = left_start, midpoint
            
            while left_index < midpoint or right_index < right_end:
                if (right_index >= right_end or 
                    (left_index < midpoint and arr[left_index] <= arr[right_index])):
                    merged.append(arr[left_index])
                    left_index += 1
                else:
                    merged.append(arr[right_index])
                    right_index += 1
                    
            for index, item in enumerate(merged, start=left_start):
                arr[index] = item
        
        width *= 2

非递归归并排序，即自底向上的归并排序，在一些特定情况下具备独特的优势。

稳定性和时间复杂度
- 归并排序无论是递归还是非递归形式都能保证O(NlogN)的时间复杂度以及稳定性。这意味着对于相同元素的数据项之间的相对位置不会因为排序而改变。
避免递归带来的系统栈开销
```
// 对比于递归版本的调用栈消耗，非递归方式更节省内存资源
void MergeSortNonR(int* arr, int size);
```
这一点使得当面对深度较大的递归场景时，非递归方案可以有效防止可能发生的栈溢出错误。
可预测的空间占用模式
虽然都需要额外O(N)级别的辅助存储空间用于临时存放待合并的小数组片段，但这种需求是可以预见并且恒定不变的，不像某些快速排序那样具有潜在的风险导致极端情况下的极高空间成本。

快速排序和归并排序都是高效且常用的排序算法，在不同场景下各有优劣，因此可以根据具体情况选择更合适的算法。

当对内存空间敏感时：
- 如果可用的额外内存有限，则应优先考虑快速排序。因为该算法可以在原地进行排序而不需要额外的空间分配。
对于稳定性有要求的情况：
- 若需要保证排序过程不会改变相等元素之间的相对顺序，则应该选用归并排序。这是因为归并排序能够保持稳定性的特性。
处理小规模数据集的情况下：
- 对于较小的数据集合（如长度不超过10），可以利用插入排序代替标准的递归式快速排序以提高效率，这在某些优化版本中有所体现。

# 示例代码展示了一个经过优化后的快速排序逻辑
def QuickSort1(arr):
    def sort(start, end):
        if (end - start) <= 10: 
            insertion_sort(arr[start:end])  # 使用插入排序优化
            return

        pivot_index = partition(arr, start, end)
        sort(start, pivot_index)
        sort(pivot_index + 1, end)

    sort(0, len(arr))

对于插入排序的应用场景可以总结如下：

对于小型数据集特别有效，因为其简单的逻辑和较小的常数因子使其在处理少量元素时表现良好
当数据本身已经部分有序时表现出色。这种情况下，插入排序能够以接近线性的时间复杂度完成任务

// 假设有一个几乎已排好序的小型数组 arr[]
int arr[] = {1, 3, 5, 6, 7, 8, 2};
for (int i = 1; i < size(arr); ++i) {
    int key = arr[i];
    int j = i - 1;

    // 移动比key大的元素一位
    while (j >= 0 && arr[j] > key) {
        arr[j + 1] = arr[j];
        j--;
    }
    
    arr[j+1] = key;
}

快速排序与插入排序各自具有独特的优势和劣势：

快速排序通常被认为更高效，尤其是在处理大规模数据集时。平均情况下，该算法的时间复杂度为 O(n log n)，使得其能够较快地完成任务。

对于小规模或几乎已经排好序的数据集合而言，插入排序可能表现得更好。这类场景下，插入排序能以接近线性的效率运行，并且因为所需移动元素的操作较少而显得更加轻便快捷。另外，折半插入排序还通过减少比较次数进一步优化性能，尽管整体时间复杂度仍然是 O(n^2)。

综上所述，在大多数应用场景尤其是大型无序数组中，快速排序往往优于插入排序；然而当面对小型或是近乎有序的数据集时，则可以选择后者来获得更好的效果。

# 示例：实现简单的快速排序与插入排序

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

# 使用示例
arr_quick = [3,6,8,10,1,2,1]
print("Quick sort result:",quick_sort(arr_quick))

arr_insertion = [3,6,8,10,1,2,1]
insertion_sort(arr_insertion)
print("Insertion sort result:",arr_insertion)