??個人主頁：個人主頁
??系列專欄：C語言試題200例
??推薦一款刷算法、筆試、面經、拿大公司offer神器?? 點擊跳轉進入網站
?作者簡介：大家好，我是碼莎拉蒂，CSDN博客專家（全站排名Top 50），阿里云博客專家、51CTO博客專家、華為云享專家

1、題目

題目：實現歸并排序算法

概念及其介紹
歸并排序（Merge sort）是建立在歸并操作上的一種有效、穩定的排序算法，該算法是采用分治法(Divide and Conquer）的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。

適用說明
當有 n 個記錄時，需進行 logn 輪歸并排序，每一輪歸并，其比較次數不超過 n，元素移動次數都是 n，因此，歸并排序的時間復雜度為 O(nlogn)。歸并排序時需要和待排序記錄個數相等的存儲空間，所以空間復雜度為 O(n)。

歸并排序適用于數據量大，并且對穩定性有要求的場景。

過程圖示