C语言试题176之实现归并排序算法

📃个人主页：个人主页
🔥系列专栏：C语言试题200例
💬推荐一款刷算法、笔试、面经、拿大公司offer神器👉 点击跳转进入网站
✅作者简介：大家好，我是码莎拉蒂，CSDN博客专家（全站排名Top 50），阿里云博客专家、51CTO博客专家、华为云享专家

1、题目

题目：实现归并排序算法

概念及其介绍
归并排序（Merge sort）是建立在归并操作上的一种有效、稳定的排序算法，该算法是采用分治法(Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

适用说明
当有 n 个记录时，需进行 logn 轮归并排序，每一轮归并，其比较次数不超过 n，元素移动次数都是 n，因此，归并排序的时间复杂度为 O(nlogn)。归并排序时需要和待排序记录个数相等的存储空间，所以空间复杂度为 O(n)。

归并排序适用于数据量大，并且对稳定性有要求的场景。

过程图示

文章来源: chenyu.blog.csdn.net，作者：码莎拉蒂 .，版权归原作者所有，如需转载，请联系作者。

原文链接：chenyu.blog.csdn.net/article/details/125193104