How to use merge sort algorithm in C++

How to use the merge sort algorithm in C

Merge sort is a classic sorting algorithm. It uses the idea of ​​​​the divide and conquer method to divide the sequence to be sorted into Sort two subsequences separately, and then merge the two ordered subsequences into one ordered sequence. Below, we will introduce how to use C language to implement the merge sort algorithm and give specific code examples.

1. Algorithm Idea

The core idea of ​​merge sort is to split the sequence to be sorted into multiple subsequences, then perform recursive call sorting on the subsequences, and finally sort the sequence. The subsequences are merged.

The specific steps are as follows:
1) If the sequence length is 1, it means it has been ordered, and returns directly
2) Divide the sequence into two subsequences equally, and make recursive calls to the two subsequences respectively. Sorting
3) Merge two ordered subsequences into one ordered sequence

2. Code example

The following is the implementation of the merge sort algorithm using C language Code example:

#include <iostream>
#include <vector>

using namespace std;

// 合并两个有序子序列
void merge(vector<int>& arr, int left, int mid, int right) {
    int i = left;    // 左子序列起始索引
    int j = mid + 1; // 右子序列起始索引
    int k = 0;       // 临时数组起始索引
    vector<int> temp(right - left + 1); // 临时数组

    // 比较两个子序列的元素，将较小的元素放入临时数组中
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }

    // 将剩余的元素复制到临时数组中
    while (i <= mid) {
        temp[k++] = arr[i++];
    }
    while (j <= right) {
        temp[k++] = arr[j++];
    }

    // 将临时数组的元素复制回原数组
    for (int m = 0; m < k; ++m) {
        arr[left + m] = temp[m];
    }
}

// 归并排序递归函数
void mergeSort(vector<int>& arr, int left, int right) {
    if (left < right) {
        int mid = (left + right) / 2;

        // 递归调用排序
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        // 合并两个有序子序列
        merge(arr, left, mid, right);
    }
}

// 归并排序函数
void mergeSort(vector<int>& arr) {
    mergeSort(arr, 0, arr.size() - 1);
}

int main() {
    vector<int> arr = {4, 6, 2, 8, 9, 1, 5, 3, 7};

    // 调用归并排序函数
    mergeSort(arr);

    // 输出排序结果
    for (int i = 0; i < arr.size(); ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;

    return 0;
}

The above code is an example of using C to implement the merge sort algorithm. First, a merge function is defined to merge two ordered subsequences. Then the mergeSort function is defined, which is used to make recursive calls for merge sorting. Finally, the mergeSort function is called in the main function to sort the sequence to be sorted and output the sorting result.

3. Summary

The merge sort algorithm is an efficient and stable sorting algorithm with a time complexity of O(nlogn). Through recursive calls and merge operations, merge sort can divide the sequence to be sorted into small blocks for sorting, and then merge the ordered subsequences into an ordered sequence. Through specific code examples implemented in C language, we can better understand and master the implementation process of the merge sort algorithm.

The above is the detailed content of How to use merge sort algorithm in C++. For more information, please follow other related articles on the PHP Chinese website!