[算法沉淀记录] 排序算法 —

排序算法 —— 归并排序

算法介绍

归并排序是一种分治算法，由约翰·冯·诺伊曼在1945年发明。它的工作原理是将未排序的列表划分为n个子列表，每个子列表包含一个元素(包含一个元素的列表被认为是有序的)，然后重复合并子列表以生成新的有序子列表，直到只剩下一个子列表。

算法基本思想

基本概念

分治法：将一个复杂的问题分解成两个或更多的相同或相似的子问题，再将子问题分成更小的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
递归：函数自身调用自身。
稳定性：如果待排序列中两个元素相等，排序后这两个相等元素的相对位置不变，则该算法是稳定的。

算法步骤

分解：将待排序的n个元素的序列分成两个子序列，每个子序列包含n/2个元素。
解决：使用归并排序递归地排序两个子序列。
合并：将两个已排序的子序列合并成一个最终的排序序列。

伪代码描述

function mergeSort(list)if length(list) <= 1return listmid <- length(list) / 2left <- mergeSort(list[0...mid])right <- mergeSort(list[mid+1...end])return merge(left, right)
end functionfunction merge(left, right)result <- empty listwhile left and right are not emptyif first(left) <= first(right)append first(left) to resultremove first element from leftelseappend first(right) to resultremove first element from rightend ifend whileappend remaining elements of left and right (if any) to resultreturn result
end function

归并排序是一种高效的排序算法，其优缺点如下：

优点

稳定性：归并排序是一种稳定的排序算法，即相同元素的相对顺序在排序后不会改变。
时间复杂度：归并排序的最坏、平均和最佳时间复杂度均为(O(n log n))，这意味着它能够提供一致的快速排序性能，不受输入数据初始顺序的影响。
适用于大量数据：由于时间复杂度较低，归并排序非常适合处理大量数据。
外部排序：归并排序特别适合外部排序，即数据量太大，无法全部加载到内存中的情况。归并排序可以分块读取数据，逐块排序，最后合并结果。

缺点

空间复杂度：归并排序的主要缺点是它需要额外的存储空间。在归并过程中，需要与原始数组大小相同的额外空间来存储临时合并的数组。因此，其空间复杂度为(O(n))。
内存使用：对于内存受限的系统，归并排序可能不是最佳选择，因为它需要足够的内存来存储临时数组。
小数组效率：对于小数组，归并排序可能不如其他简单排序算法（如插入排序）效率高。尽管时间复杂度相同，但归并排序的常数因子较大，因为它涉及到递归和合并操作。
递归开销：如果使用递归实现，归并排序可能会受到递归调用的开销影响，尤其是在深度较大的情况下。尽管现代编译器和操作系统对递归有很好的优化，但非递归实现可以避免这种开销。

总体而言，归并排序是一种高效的通用排序算法，特别适合需要稳定排序和大量数据的情况。然而，如果内存使用是一个关键因素，或者数据集非常小，可能需要考虑其他排序算法。

应用场景

归并排序是一种高效的通用排序算法，由于其稳定性和(O(n log n))的时间复杂度，它在多种应用场景中都非常适用。以下是一些归并排序的常见应用场景：

大数据集排序：归并排序非常适合处理大量数据的排序问题，尤其是当数据集无法一次性加载到内存中时，可以使用外部归并排序。
并发编程：在多线程或分布式系统中，归并排序可以很容易地并行化。每个线程或进程可以独立地排序数据的一部分，然后合并结果。
数据库系统：数据库管理系统中的排序操作经常使用归并排序，因为它可以提供稳定的排序结果，这对于数据库的完整性非常重要。
文件排序：在需要对大量文件进行排序时，归并排序是一个很好的选择。文件可以分块读取到内存中，排序后再合并。
算法教学：归并排序是计算机科学教育中常用的教学示例，用于讲解分治策略和递归思想。
网络数据传输：在网络数据传输中，为了保证数据的顺序，可以使用归并排序对分段传输的数据进行排序。
数值计算：在科学计算和工程应用中，经常需要处理大量的数值数据，归并排序可以有效地对这些数据进行排序。
操作系统：操作系统的文件系统或虚拟内存管理等组件可能会使用归并排序来管理数据。
编译器优化：编译器在优化代码时，可能会使用归并排序来处理符号表或优化指令序列。
多媒体数据处理：在多媒体数据的管理和播放中，如音频剪辑、视频编辑等，归并排序可以用来对数据片段进行排序。

尽管归并排序在许多场景中都非常适用，但它也有一些局限性。例如，归并排序需要额外的存储空间，这在内存受限的环境中可能是一个问题。此外，对于小数据集，归并排序可能不如其他简单的排序算法（如插入排序）效率高，因为归并排序的常数因子较大。因此，在实际应用中，通常会根据具体的需求和数据特性来选择最合适的排序算法。

时间复杂度

归并排序的时间复杂度在最好情况、最坏情况和平均情况下的表现如下

最好情况

最好情况发生在输入数组已经是有序的情况下。在这种情况下，每个子数组都是有序的，所以合并操作会非常快，只需要一次比较就可以将两个子数组合并成一个有序数组。但是，分割过程仍然需要执行 (log(n)) 次，因为我们需要将整个数组分成两个有序的子数组。因此，最好情况下的时间复杂度是 (O(n))。

最坏情况

最坏情况发生在输入数组是完全逆序的情况下。在这种情况下，每次合并操作都需要比较和移动所有的元素，因为我们需要将最大的元素移动到数组的末尾。因此，最坏情况下的时间复杂度是 (O(nlog(n)))。

平均情况

平均情况下，输入数组的元素是随机排列的。在这种情况下，归并排序的时间复杂度仍然是 (O(nlog(n)))。这是因为尽管某些合并操作可能比最好情况下的时间复杂度高，但平均来看，每个元素仍然只需要比较和移动 (log(n)) 次。

小结：

最好情况：(O(n))
最坏情况：(O(n log n))
平均情况：(O(n log n))

归并排序的时间复杂度不受输入数据初始顺序的影响，因为它总是需要进行 (log(n)) 次分割，并且每次合并操作的复杂度是 (O(n))。因此，归并排序是一个稳定的排序算法，其性能在各种情况下都是可预测的。

归并排序的时间复杂度主要由两部分组成：分割和合并。

分割：分割过程是一个递归过程，它将数组分成越来越小的部分，直到每个部分只包含一个元素。这个分割过程会执行 (log(n)) 次，因为每次分割都会将数组大小减半。
合并：合并过程将两个有序数组合并成一个有序数组。在合并过程中，每个元素最多比较和移动一次。对于每个级别的分割，合并操作的总次数是 (n)，因为每次合并都会处理整个数组。

综合以上两点，归并排序的时间复杂度是 (O(n log n))。这是因为分割过程的时间复杂度是 O(log n)，而合并过程的时间复杂度是 (O(n))，所以总的时间复杂度是 (O(n log n))。

空间复杂度

归并排序的空间复杂度主要由合并过程中的临时数组决定。

临时数组：在合并两个有序数组时，需要一个与待排序数组大小相同的临时数组来存储合并的结果。这个临时数组在合并完成后会被复制回原数组。

因此，归并排序的空间复杂度是 (O(n))，因为它需要一个额外的数组来存储合并过程中的临时结果。

证明

我们可以通过数学归纳法来证明归并排序的时间复杂度是 (O(n log n))。
基础情况：当数组大小为 1 时，不需要排序，时间复杂度为 O(1)。
归纳假设：假设对于大小为 k 的数组，归并排序的时间复杂度是 O(k log k)。
归纳步骤：对于大小为 2k 的数组，我们将其分成两个大小为 k 的子数组，分别对它们进行排序，然后合并。根据归纳假设，每个子数组的排序时间是 O(k log k)，合并时间是 O(k)。因此，总的时间复杂度是 O(k log k + k) = O(k log k) = O((2k) log (2k)) = (O(n log n))。
由于每次递归都会将数组大小减半，所以每次递归的时间复杂度都是 (O(n log n))。因此，归并排序的时间复杂度是 (O(n log n))。
空间复杂度的证明类似，每次合并都需要一个大小为 n 的临时数组，所以总的空间复杂度是 (O(n))。
综上所述，归并排序的时间复杂度是 (O(n log n))，空间复杂度是 (O(n))。

代码实现

Python 实现

递归版本

多个函数版：

def merge(left, right):# Create an empty array to store the merged elementsmerged = []# Initialize indexes for the left and right subarraysleft_index = 0right_index = 0# Compare elements of the left and right subarrays and add them to the merged arraywhile left_index < len(left) and right_index < len(right):if left[left_index] <= right[right_index]:merged.append(left[left_index])left_index += 1else:merged.append(right[right_index])right_index += 1# Add the remaining elements of the left subarray to the merged arraymerged += left[left_index:]# Add the remaining elements of the right subarray to the merged arraymerged += right[right_index:]# Return the merged arrayreturn mergeddef merge_sort(lst):# Check if the length of the array is less than or equal to 1if len(lst) <= 1:# Return the array if it isreturn lst# Calculate the midpoint of the arraymid = len(lst) // 2# Create two subarrays, one from the start to the midpoint and one from the midpoint to the endleft = merge_sort(lst[:mid])right = merge_sort(lst[mid:])# Merge the two subarrays and return the sorted arrayreturn merge(left, right)

单个函数版：

def mergeSort(arr):# Check if the length of the array is greater than 1if len(arr) > 1:# Calculate the midpoint of the arraymid = len(arr) // 2# Create two subarrays, one from the start to the midpoint and one from the midpoint to the endleft = arr[:mid]right = arr[mid:]# Recursively call the mergeSort function on each subarraymergeSort(left)mergeSort(right)# Initialize indexes for the left and right subarraysi = j = k = 0# Compare elements of the left and right subarrays and add them to the sorted arraywhile i < len(left) and j < len(right):if left[i] < right[j]:arr[k] = left[i]i += 1else:arr[k] = right[j]j += 1k += 1# Add the remaining elements of the left subarray to the sorted arraywhile i < len(left):arr[k] = left[i]i += 1k += 1# Add the remaining elements of the right subarray to the sorted arraywhile j < len(right):arr[k] = right[j]j += 1k += 1

非递归版本

def mergeNew(arr, l, m, r):n1 = m - l + 1n2 = r - mL = [0] * n1R = [0] * n2for i in range(0, n1):L[i] = arr[l + i]for j in range(0, n2):R[j] = arr[m + 1 + j]i, j, k = 0, 0, lwhile i < n1 and j < n2:if L[i] <= R[j]:arr[k] = L[i]i += 1else:arr[k] = R[j]j += 1k += 1while i < n1:arr[k] = L[i]i += 1k += 1while j < n2:arr[k] = R[j]j += 1k += 1def merge_sort_bottom_up(arr):n = len(arr)size = 1while size <= n - 1:for left_start in range(0, n - 1, 2 * size):mid = min(left_start + size - 1, n - 1)right_end = min(left_start + 2 * size - 1, n - 1)mergeNew(arr, left_start, mid, right_end)size = size * 2

C++ 实现

C++ 模板实现

递归版本

template <typename T>
vector<T> merge(vector<T> &left, vector<T> &right)
{vector<T> merged;while (!left.empty() && !right.empty()){// Compare the first elements of the two sublistsif (left[0] <= right[0]){// If left sublist's element is smaller, add it to the merged sublistmerged.push_back(left[0]);// Erase the element from the sublistleft.erase(left.begin());}else{// If right sublist's element is smaller, add it to the merged sublistmerged.push_back(right[0]);// Erase the element from the sublistright.erase(right.begin());}}// Add the remaining elements of the left sublist to the merged sublistmerged.insert(merged.end(), left.begin(), left.end());// Add the remaining elements of the right sublist to the merged sublistmerged.insert(merged.end(), right.begin(), right.end());return merged;
}template <typename T>
vector<T> mergeSort(const vector<T> &list)
{// If the list has one or less elements, it is already sortedif (list.size() <= 1){return list;}// Find the midpoint of the listint mid = list.size() / 2;// Create two sublists, one from the beginning to the midpoint, and one from the midpoint to the endvector<T> left = mergeSort(vector<T>(list.begin(), list.begin() + mid));vector<T> right = mergeSort(vector<T>(list.begin() + mid, list.end()));// Merge the two sublists and return the sorted listreturn merge(left, right);
}

非递归版本

template <typename T>
void mergeSortNonRecursive(vector<T> &arr)
{// 1. Find the size of the arrayint n = arr.size();// 2. Iterate through the arrayfor (int size = 1; size < n; size *= 2){// 3. Iterate through the arrayfor (int leftStart = 0; leftStart < n - size; leftStart += 2 * size){// 4. Find the mid pointint mid = min(leftStart + size, n);// 5. Find the right start pointint rightStart = min(leftStart + 2 * size, n);// 6. Create a temporary arrayint i = leftStart;int j = mid;int k = leftStart;vector<T> temp(arr.begin(), arr.end());// 7. Compare the elements and move them to the temporary arraywhile (i < mid && j < rightStart){if (arr[i] <= arr[j]){temp[k++] = arr[i++];}else{temp[k++] = arr[j++];}}// 8. Move the remaining elements to the temporary arraywhile (i < mid){temp[k++] = arr[i++];}while (j < rightStart){temp[k++] = arr[j++];}// 9. Copy the elements from the temporary array to the original arraycopy(temp.begin(), temp.end(), arr.begin());}}
}

扩展阅读

优化时间复杂度的思路

时间复杂度优化

最小化复制操作：在归并过程中，可以减少不必要的数据复制。例如，可以使用指针而不是实际复制数据来合并两个子数组。
局部性优化：利用数据的局部性原理，优先合并相邻的小数组块，这样可以提高缓存利用率。
切换到插入排序：对于小数组，归并排序的常数因子较大，可以切换到插入排序来处理小数组，因为插入排序在小数组上通常表现得更好。
并行化：归并排序可以很容易地并行化，尤其是在合并阶段，可以同时对多个子数组进行合并。

空间复杂度优化

原地归并：通过使用额外的几个变量，可以在原地完成归并操作，从而将空间复杂度从(O(n))降低到O(1)。这通常会增加算法的复杂性。
使用迭代而非递归：迭代版本的归并排序可以避免递归带来的额外空间开销。

归并排序的变种算法

自底向上的归并排序：这是一种非递归的归并排序，它从最小的数组块开始合并，逐步增加块的大小，直到整个数组被排序。
多路归并排序：传统的归并排序是两路归并，即每次合并两个子数组。多路归并排序可以同时合并多个子数组，这可以进一步提高合并阶段的效率，尤其是在并行计算中。
外部归并排序：当数据集太大而无法全部加载到内存中时，可以使用外部归并排序。这种算法将数据分块存储在磁盘上，然后分块读取、排序并合并。
Timsort：Timsort是Python和Java标准库中使用的排序算法，它是归并排序和插入排序的结合。Timsort利用了现实世界数据通常部分有序的特点，通过优化来提高排序效率。
历史上，归并排序的变种算法还包括一些针对特定应用场景的优化，例如在数据库排序、多核处理器排序等方面的变种。这些变种算法通常结合了特定硬件特性和数据特征来进一步提高排序效率。

自底向上的归并排序（Bottom-Up Merge Sort）

自底向上的归并排序（Bottom-Up Merge Sort）是一种非递归的归并排序算法。它与传统的递归归并排序不同，不是一开始就将数组分成单个元素的小数组，然后再两两合并，而是从最小的数组块开始，逐步合并成更大的有序块，直到整个数组排序完成。

算法步骤

初始化：将数组分解成n个长度为1的子数组（每个元素都是一个子数组）。
迭代合并：重复以下过程，直到所有子数组合并成一个有序数组：
- 合并相邻的子数组对，每个子数组的长度是上一次合并的长度的两倍。
- 每次合并后，子数组的数量减半，每个子数组的长度加倍。
完成排序：当数组完全合并时，排序完成。

伪代码

自底向上的归并排序(A)n = A的长度size = 1  // 初始子数组大小while size < np = 0  // 子数组的起始索引while p + size < nq = p + size - 1  // 第一个子数组的结束索引r = min((p + 2 * size - 1), (n - 1))  // 第二个子数组的结束索引合并(A, p, q, r)p = r + 1  // 更新下一个子数组的起始索引size = size * 2  // 子数组大小翻倍

Python 代码实现

def mergeNew(arr, l, m, r):n1 = m - l + 1n2 = r - mL = [0] * n1R = [0] * n2for i in range(0, n1):L[i] = arr[l + i]for j in range(0, n2):R[j] = arr[m + 1 + j]i, j, k = 0, 0, lwhile i < n1 and j < n2:if L[i] <= R[j]:arr[k] = L[i]i += 1else:arr[k] = R[j]j += 1k += 1while i < n1:arr[k] = L[i]i += 1k += 1while j < n2:arr[k] = R[j]j += 1k += 1def merge_sort_bottom_up(arr):n = len(arr)size = 1while size <= n - 1:for left_start in range(0, n - 1, 2 * size):mid = min(left_start + size - 1, n - 1)right_end = min(left_start + 2 * size - 1, n - 1)mergeNew(arr, left_start, mid, right_end)size = size * 2

C++模板代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// 合并两个有序数组A[p...q]和A[q+1...r]
template <typename T>
void Merge(vector<T>& A, int p, int q, int r) {int n1 = q - p + 1;int n2 = r - q;vector<T> L(n1);vector<T> R(n2);for (int i = 0; i < n1; i++) {L[i] = A[p + i];}for (int j = 0; j < n2; j++) {R[j] = A[q + 1 + j];}int i = 0, j = 0;for (int k = p; k <= r; k++) {if (i < n1 && (j >= n2 || L[i] <= R[j])) {A[k] = L[i];i++;} else {A[k] = R[j];j++;}}
}// 自底向上的归并排序
template <typename T>
void MergeSortBottomUp(vector<T>& A) {int n = A.size();for (int size = 1; size < n; size *= 2) {for (int leftStart = 0; leftStart < n - size; leftStart += 2 * size) {int mid = leftStart + size - 1;int rightEnd = min(leftStart + 2 * size - 1, n - 1);Merge(A, leftStart, mid, rightEnd);}}
}int main() {vector<int> arr = {5, 2, 4, 7, 1, 3, 2, 6};MergeSortBottomUp(arr);for (int i = 0; i < arr.size(); i++) {cout << arr[i] << " ";}cout << endl;return 0;
}

这段代码定义了一个模板函数MergeSortBottomUp，它接受一个vector类型的参数arr，并对其进行自底向上的归并排序。函数使用两层循环：外层循环控制子数组的大小，内层循环遍历数组并合并相邻的子数组。在合并过程中，使用了一个临时数组L和R来存储合并前的子数组，然后再将合并后的结果复制回原数组arr。
在main函数中，我们创建了一个整数类型的vector，并调用MergeSortBottomUp进行排序，最后输出排序后的数组。

多路归并排序(Multi-way Merge Sort)

多路归并排序（Multi-Way Merge Sort）是一种改进的归并排序算法，它能够同时合并多个有序的子数组，而不是传统的归并排序中每次只合并两个子数组。这种方法可以显著提高大规模数据集的排序效率。

基本概念

多路归并排序的核心思想是将多个有序的子数组合并成一个有序的大数组。它通常用于处理数据量非常大，以至于无法全部放入内存的情况。与传统的归并排序相比，多路归并排序可以在每个阶段并行处理更多的数据，从而减少整体排序时间。

算法步骤

初始化：将数据集分割成多个子数组。
分组归并：将多个子数组合并为较大的有序子数组，直到只剩下一个子数组。
最终归并：将最后剩余的有序子数组合并成一个最终的有序数组。

伪代码

多路归并排序(A)n = A的长度k = 子数组的数量  // 通常设置为处理器的数量或数据块的数量大小 = 数据集大小 / k将A分割成k个子数组，每个大小为大小while 子数组的数量 > 1合并相邻的子数组对，直到只剩下一个子数组子数组的数量 = 子数组数量 / 2返回有序的A

C++模板代码实现

template <typename T>
void multiwayMergeSort(vector<T> &arr, int k)
{int n = arr.size();if (n <= 1)return;vector<vector<T>> segments(k);for (int i = 0; i < n; ++i){segments[i % k].push_back(arr[i]);}for (auto &segment : segments){multiwayMergeSort(segment, k);}priority_queue<pair<T, int>, vector<pair<T, int>>, greater<>> pq;vector<int> indices(k, 0);for (int i = 0; i < k; ++i){if (!segments[i].empty()){pq.push({segments[i][0], i});indices[i]++;}}arr.clear();while (!pq.empty()){auto [val, idx] = pq.top();pq.pop();arr.push_back(val);if (indices[idx] < segments[idx].size()){pq.push({segments[idx][indices[idx]], idx});indices[idx]++;}}
}template <typename T>
void multiway_merge_sort_non_recursive(vector<T> &data)
{int k = data.size();int current_size = 1; // Start with smallest sub-list size// Repeatedly merge sub-lists of increasing sizewhile (current_size < k){for (int left = 0; left < k; left += current_size * 2){// Calculate right and mid indices for the current mergeint mid = min(left + current_size, k);int right = min(left + current_size * 2, k);// Merge sub-lists [left, mid) and [mid, right)auto left_it = data.begin() + left, mid_it = data.begin() + mid;auto right_it = (right < k) ? data.begin() + right : data.end();// Create temporary vector for merged elementsvector<T> merged;// Merge elements until one sub-list is exhaustedwhile (left_it != data.begin() + mid && mid_it != data.begin() + right){if (*left_it <= *mid_it){merged.push_back(*left_it);++left_it;}else{merged.push_back(*mid_it);++mid_it;}}// Add remaining elements from the non-exhausted sub-listmerged.insert(merged.end(), left_it, data.begin() + mid);if (right_it != mid_it){merged.insert(merged.end(), right_it, data.end());}// Update the original data with the merged elementscopy(merged.begin(), merged.end(), data.begin() + left);}current_size *= 2; // Double the sub-list size for next merge}
}

完整代码

#include <iostream>
#include <array>
#include <algorithm>
#include <vector>
#include <string>
#include <vector>
#include <queue>using namespace std;class Person
{
public:Person() = default;Person(string name, int age, int score){this->name = name;this->age = age;this->socre = score;}// Override the operator> for other function to use.bool operator>(const Person &other) const{// Compare the socre of two Person objects.return this->socre > other.socre;}// Override the operator< for other function to use.bool operator<(const Person &other) const{// Compare the socre of two Person objects.return this->socre < other.socre;}// Override the operator== for other function to use.bool operator==(const Person &other) const{// Compare the socre, age and name of two Person objects.return this->socre == other.socre &&this->age == other.age &&this->name == other.name;}// Override the operator!= for other function to use.bool operator!=(const Person &other) const{// Compare the socre, age and name of two Person objects.return this->socre != other.socre ||this->age != other.age ||this->name != other.name;}// Override the operator<= for other fnction to use.bool operator<=(const Person &other) const{// Compare the socre, age and name of two Person objects.return this->socre <= other.socre &&this->age <= other.age &&this->name <= other.name;}// Override the operator>= for other function to use.bool operator>=(const Person &other) const{// Compare the socre, age and name of two Person objects.return this->socre >= other.socre &&this->age >= other.age &&this->name >= other.name;}// Now there are some get parameters function for this calss:const string &getName() const { return this->name; }int getAge() const { return this->age; }int getScore() const { return this->socre; }private:string name;int age = 0;int socre = 0;
};template <typename T>
vector<T> merge(vector<T> &left, vector<T> &right)
{vector<T> merged;while (!left.empty() && !right.empty()){// Compare the first elements of the two sublistsif (left[0] <= right[0]){// If left sublist's element is smaller, add it to the merged sublistmerged.push_back(left[0]);// Erase the element from the sublistleft.erase(left.begin());}else{// If right sublist's element is smaller, add it to the merged sublistmerged.push_back(right[0]);// Erase the element from the sublistright.erase(right.begin());}}// Add the remaining elements of the left sublist to the merged sublistmerged.insert(merged.end(), left.begin(), left.end());// Add the remaining elements of the right sublist to the merged sublistmerged.insert(merged.end(), right.begin(), right.end());return merged;
}template <typename T>
vector<T> mergeSort(const vector<T> &list)
{// If the list has one or less elements, it is already sortedif (list.size() <= 1){return list;}// Find the midpoint of the listint mid = list.size() / 2;// Create two sublists, one from the beginning to the midpoint, and one from the midpoint to the endvector<T> left = mergeSort(vector<T>(list.begin(), list.begin() + mid));vector<T> right = mergeSort(vector<T>(list.begin() + mid, list.end()));// Merge the two sublists and return the sorted listreturn merge(left, right);
}void mergeSortTestCase()
{vector<int> data = {9, 8, 3, 7, 5, 6, 4, 1};mergeSort<int>(data);for (int i : data){cout << i << " ";}cout << endl;vector<double> dData = {9.9, 9.1, 3.3, 7.7, 5.5, 6.6, 4.4, 1.1};mergeSort<double>(dData);for (double i : dData){cout << i << " ";}cout << endl;vector<char> cData = {'a', 'c', 'b', 'd', 'e'};mergeSort<char>(cData);for (char i : cData){cout << i << " ";}cout << endl;vector<Person> pData = {Person("Alice", 20, 90), Person("Bob", 18, 85), Person("Charlie", 22, 95)};mergeSort<Person>(pData);for (Person i : pData){cout << i.getName() << " " << i.getAge() << " " << i.getScore() << endl;}cout << endl;
}template <typename T>
vector<T> mergeOther(const vector<T> &left, const vector<T> &right)
{vector<T> result;unsigned left_it = 0, right_it = 0;while (left_it < left.size() && right_it < right.size()){// compare the current elements of the left and right vectorsif (left[left_it] < right[right_it]){// if the element of the left vector is less than the element of the right vector, add it to the result vectorresult.push_back(left[left_it]);left_it++;}else{// if the element of the left vector is greater than or equal to the element of the right vector, add it to the result vectorresult.push_back(right[right_it]);right_it++;}}// add the remaining elements of the left vector to the result vectorwhile (left_it < left.size()){result.push_back(left[left_it]);left_it++;}// add the remaining elements of the right vector to the result vectorwhile (right_it < right.size()){result.push_back(right[right_it]);right_it++;}return result;
}template <typename T>
vector<T> mergeSortOther(vector<T> &arr)
{// if the vector is empty or contains only one element, return the vectorif (arr.size() <= 1){return arr;}// create two vectors, one to store the elements of the original vector before the split and one to store the elements after the splitvector<T> left, right, result;int middle = ((int)arr.size() + 1) / 2;// copy the elements of the original vector into the left vectorfor (int i = 0; i < middle; i++){left.push_back(arr[i]);}// copy the elements of the original vector into the right vectorfor (int i = middle; i < arr.size(); i++){right.push_back(arr[i]);}// call the mergeSortOther function on the left and right vectorsleft = mergeSortOther(left);right = mergeSortOther(right);// call the mergeOther function to merge the sorted left and right vectorsresult = mergeOther(left, right);// return the merged sorted vectorreturn result;
}void mergeSortOtherTestCase()
{vector<int> data = {9, 8, 3, 7, 5, 6, 4, 1};mergeSortOther<int>(data);for (int i : data){cout << i << " ";}cout << endl;vector<double> dData = {9.9, 9.1, 3.3, 7.7, 5.5, 6.6, 4.4, 1.1};mergeSortOther<double>(dData);for (double i : dData){cout << i << " ";}cout << endl;vector<char> cData = {'a', 'c', 'b', 'd', 'e'};mergeSortOther<char>(cData);for (char i : cData){cout << i << " ";}cout << endl;vector<Person> pData = {Person("Alice", 20, 90), Person("Bob", 18, 85), Person("Charlie", 22, 95)};mergeSortOther<Person>(pData);for (Person i : pData){cout << i.getName() << " " << i.getAge() << " " << i.getScore() << endl;}cout << endl;
}template <typename T>
void mergeSortNonRecursive(vector<T> &arr)
{// 1. Find the size of the arrayint n = arr.size();// 2. Iterate through the arrayfor (int size = 1; size < n; size *= 2){// 3. Iterate through the arrayfor (int leftStart = 0; leftStart < n - size; leftStart += 2 * size){// 4. Find the mid pointint mid = min(leftStart + size, n);// 5. Find the right start pointint rightStart = min(leftStart + 2 * size, n);// 6. Create a temporary arrayint i = leftStart;int j = mid;int k = leftStart;vector<T> temp(arr.begin(), arr.end());// 7. Compare the elements and move them to the temporary arraywhile (i < mid && j < rightStart){if (arr[i] <= arr[j]){temp[k++] = arr[i++];}else{temp[k++] = arr[j++];}}// 8. Move the remaining elements to the temporary arraywhile (i < mid){temp[k++] = arr[i++];}while (j < rightStart){temp[k++] = arr[j++];}// 9. Copy the elements from the temporary array to the original arraycopy(temp.begin(), temp.end(), arr.begin());}}
}void mergeSortNonRecursiveTestCase()
{vector<int> data = {9, 8, 3, 7, 5, 6, 4, 1};mergeSortNonRecursive<int>(data);for (int i : data){cout << i << " ";}cout << endl;vector<double> dData = {9.9, 9.1, 3.3, 7.7, 5.5, 6.6, 4.4, 1.1};mergeSortNonRecursive<double>(dData);for (double i : dData){cout << i << " ";}cout << endl;vector<char> cData = {'a', 'c', 'b', 'd', 'e'};mergeSortNonRecursive<char>(cData);for (char i : cData){cout << i << " ";}cout << endl;vector<Person> pData = {Person("Alice", 20, 90), Person("Bob", 18, 85), Person("Charlie", 22, 95)};mergeSortNonRecursive<Person>(pData);for (Person i : pData){cout << i.getName() << " " << i.getAge() << " " << i.getScore() << endl;}cout << endl;
}template <typename T>
void Merge(vector<T> &A, int p, int q, int r)
{// n1 is the size of the left sub arrayint n1 = q - p + 1;// n2 is the size of the right sub arrayint n2 = r - q;// Create two sub arrays L and R of size n1 and n2 respectivelyvector<T> L(n1);vector<T> R(n2);// Copy the elements of A from p to q into Lfor (int i = 0; i < n1; i++){L[i] = A[p + i];}// Copy the elements of A from q+1 to r into Rfor (int j = 0; j < n2; j++){R[j] = A[q + 1 + j];}// Initialize indexes i and j to 0int i = 0, j = 0;// Merge the elements of L and R into Afor (int k = p; k <= r; k++){// If the element at index i of L is less than or equal to the element at index j of Rif (i < n1 && (j >= n2 || L[i] <= R[j])){// Copy the element at index i of L into AA[k] = L[i];// Increment ii++;}else{// Copy the element at index j of R into AA[k] = R[j];// Increment jj++;}}
}template <typename T>
void MergeSortBottomUp(vector<T> &A)
{// n is the size of the array Aint n = A.size();// Iterate through the array A in a bottom up mannerfor (int size = 1; size < n; size *= 2){// Iterate through the array A in a pair of sub arraysfor (int leftStart = 0; leftStart < n - size; leftStart += 2 * size){// mid is the mid point of the left sub arrayint mid = leftStart + size - 1;// rightEnd is the rightmost element of the right sub arrayint rightEnd = min(leftStart + 2 * size - 1, n - 1);// Merge the elements of the left and right sub arrays into AMerge<T>(A, leftStart, mid, rightEnd);}}
}void mergeSortBottomUpTestCase()
{vector<int> data = {9, 8, 3, 7, 5, 6, 4, 1};MergeSortBottomUp<int>(data);for (int i : data){cout << i << " ";}cout << endl;vector<double> dData = {9.9, 9.1, 3.3, 7.7, 5.5, 6.6, 4.4, 1.1};MergeSortBottomUp<double>(dData);for (double i : dData){cout << i << " ";}cout << endl;vector<char> cData = {'a', 'c', 'b', 'd', 'e'};MergeSortBottomUp<char>(cData);for (char i : cData){cout << i << " ";}cout << endl;vector<Person> pData = {Person("Alice", 20, 90), Person("Bob", 18, 85), Person("Charlie", 22, 95)};MergeSortBottomUp<Person>(pData);for (Person i : pData){cout << i.getName() << " " << i.getAge() << " " << i.getScore() << endl;}cout << endl;
}// Helper function for merging sub-lists
template <typename T>
void merge_bottom_up_sublist(vector<T> &data, size_t left, size_t mid, size_t right)
{// Create temporary vector for holding merged elementsvector<T> temp(right - left);// Copy elements from left and right sub-lists to the temp vectorsize_t i = left, j = mid, k = 0;while (i < mid && j < right){if (data[i] <= data[j]){temp[k++] = data[i++];}else{temp[k++] = data[j++];}}// Copy remaining elements from left sub-listwhile (i < mid){temp[k++] = data[i++];}// Copy remaining elements from right sub-listwhile (j < right){temp[k++] = data[j++];}// Copy merged elements back to the original vectorcopy(temp.begin(), temp.end(), data.begin() + left);
}template <typename T>
void merge_sort_bottom_up_non_recursive(vector<T> &data)
{size_t n = data.size();// Iterate through sub-list sizes from 1 to n/2for (size_t sub_size = 1; sub_size <= n / 2; sub_size *= 2){// Iterate through the data starting from left indexfor (size_t left = 0; left < n - sub_size; left += 2 * sub_size){// Calculate right and mid indices for the mergesize_t mid = min(left + sub_size, n);size_t right = min(left + 2 * sub_size, n);// Perform the merge operationmerge_bottom_up_sublist<T>(data, left, mid, right);}}
}void merge_sort_bottom_up_non_recursive_test_case()
{vector<int> data = {9, 8, 3, 7, 5, 6, 4, 1};merge_sort_bottom_up_non_recursive<int>(data);for (int i : data){cout << i << " ";}cout << endl;vector<double> dData = {9.9, 9.1, 3.3, 7.7, 5.5, 6.6, 4.4, 1.1};merge_sort_bottom_up_non_recursive<double>(dData);for (double i : dData){cout << i << " ";}cout << endl;vector<char> cData = {'a', 'c', 'b', 'd', 'e'};merge_sort_bottom_up_non_recursive<char>(cData);for (char i : cData){cout << i << " ";}cout << endl;vector<Person> pData = {Person("Alice", 20, 90), Person("Bob", 18, 85), Person("Charlie", 22, 95)};merge_sort_bottom_up_non_recursive<Person>(pData);for (Person i : pData){cout << i.getName() << " " << i.getAge() << " " << i.getScore() << endl;}cout << endl;
}template <typename T>
void multiwayMergeSort(vector<T> &arr, int k)
{int n = arr.size();if (n <= 1)return;vector<vector<T>> segments(k);for (int i = 0; i < n; ++i){segments[i % k].push_back(arr[i]);}for (auto &segment : segments){multiwayMergeSort(segment, k);}priority_queue<pair<T, int>, vector<pair<T, int>>, greater<>> pq;vector<int> indices(k, 0);for (int i = 0; i < k; ++i){if (!segments[i].empty()){pq.push({segments[i][0], i});indices[i]++;}}arr.clear();while (!pq.empty()){auto [val, idx] = pq.top();pq.pop();arr.push_back(val);if (indices[idx] < segments[idx].size()){pq.push({segments[idx][indices[idx]], idx});indices[idx]++;}}
}void multiWayMergeSortTestCase()
{int mutilWayConunt = 4;vector<int> data = {9, 8, 3, 7, 5, 6, 4, 1};multiwayMergeSort<int>(data, mutilWayConunt);for (int i : data){cout << i << " ";}cout << endl;vector<double> dData = {9.9, 9.1, 3.3, 7.7, 5.5, 6.6, 4.4, 1.1};multiwayMergeSort<double>(dData, mutilWayConunt);for (double i : dData){cout << i << " ";}cout << endl;vector<char> cData = {'a', 'c', 'b', 'd', 'e'};multiwayMergeSort<char>(cData, mutilWayConunt);for (char i : cData){cout << i << " ";}cout << endl;vector<Person> pData = {Person("Alice", 20, 90), Person("Bob", 18, 85), Person("Charlie", 22, 95)};multiwayMergeSort<Person>(pData, mutilWayConunt);for (Person i : pData){cout << i.getName() << " " << i.getAge() << " " << i.getScore() << endl;}cout << endl;
}template <typename T>
void multiway_merge_sort_non_recursive(vector<T> &data)
{int k = data.size();int current_size = 1; // Start with smallest sub-list size// Repeatedly merge sub-lists of increasing sizewhile (current_size < k){for (int left = 0; left < k; left += current_size * 2){// Calculate right and mid indices for the current mergeint mid = min(left + current_size, k);int right = min(left + current_size * 2, k);// Merge sub-lists [left, mid) and [mid, right)auto left_it = data.begin() + left, mid_it = data.begin() + mid;auto right_it = (right < k) ? data.begin() + right : data.end();// Create temporary vector for merged elementsvector<T> merged;// Merge elements until one sub-list is exhaustedwhile (left_it != data.begin() + mid && mid_it != data.begin() + right){if (*left_it <= *mid_it){merged.push_back(*left_it);++left_it;}else{merged.push_back(*mid_it);++mid_it;}}// Add remaining elements from the non-exhausted sub-listmerged.insert(merged.end(), left_it, data.begin() + mid);if (right_it != mid_it){merged.insert(merged.end(), right_it, data.end());}// Update the original data with the merged elementscopy(merged.begin(), merged.end(), data.begin() + left);}current_size *= 2; // Double the sub-list size for next merge}
}void multiway_merge_sort_non_recursive_test_case()
{vector<int> data = {9, 8, 3, 7, 5, 6, 4, 1};multiway_merge_sort_non_recursive<int>(data);for (int i : data){cout << i << " ";}cout << endl;vector<double> dData = {9.9, 9.1, 3.3, 7.7, 5.5, 6.6, 4.4, 1.1};multiway_merge_sort_non_recursive<double>(dData);for (double i : dData){cout << i << " ";}cout << endl;vector<char> cData = {'a', 'c', 'b', 'd', 'e'};multiway_merge_sort_non_recursive<char>(cData);for (char i : cData){cout << i << " ";}cout << endl;vector<Person> pData = {Person("Alice", 20, 90), Person("Bob", 18, 85), Person("Charlie", 22, 95)};multiway_merge_sort_non_recursive<Person>(pData);for (Person i : pData){cout << i.getName() << " " << i.getAge() << " " << i.getScore() << endl;}cout << endl;
}int main()
{mergeSortTestCase();mergeSortNonRecursiveTestCase();mergeSortOtherTestCase();mergeSortBottomUpTestCase();multiWayMergeSortTestCase();multiway_merge_sort_non_recursive_test_case();merge_sort_bottom_up_non_recursive_test_case();return 0;
}