前言

一种将无序数组进行排序的方法。

归并排序，相关定义可以参考wiki：
https://zh.wikipedia.org/wiki/%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F

主要思想有2：

1. 有序数组。在插入排序中也有此思想
2. 合并两两有序数组，通过引入额外的临时数组实现。

本文代码基本未优化，是一种原始逻辑的体现。

环境

编辑器：vs2019
文件：.c类型

正文

代码参考：

#include <stdio.h>


// 归并排序，主要思想：合并两个有序数组，通过引入额外的临时数组实现。
// 递归归并排序，每一次递归，改变一次有序数组长度。


// 普通归并排序，从小到大
void merge_sort_normal(int source_array[], int source_array_length)
{
    int start; // 两两分组的总起点索引
    int* b = (int*)malloc(source_array_length * sizeof(int)); // 引入临时数组， 临时数组存放每次排序后的结果。

    // 分组, 每组元素数量：1, 2, 4, 8 ...
    for (int gap = 1; gap < source_array_length; gap += gap)
    {
        // 合并两两分组
        for (start = 0; start < source_array_length; start += gap * 2)
        {
            // 临时数组的索引
            int b_index = start;

            // 左边数组的起点索引
            int start_left = start;
            // 左边数组的结束索引
            int end_left = start_left + gap - 1;

            // 右边数组的起点索引
            int start_right = start + gap;
            // 右边数组的结束索引
            int end_right = start_right + gap - 1;

            // 1. 当左边数组不满时,或没有右边数组时
            if (end_left >= source_array_length - 1)
            {
                for (; b_index < source_array_length; b_index++)
                {
                    b[b_index] = source_array[b_index];
                }
                break;
            }

            // 2. 当右边数组不满时
            if (end_right > source_array_length - 1)
            {
                end_right = source_array_length - 1;
            }

            // 3. 开始合并两数组
            while (start_left <= end_left && start_right <= end_right)
            {
                if (source_array[start_right] > source_array[start_left])
                {
                    b[b_index] = source_array[start_left];
                    b_index++;
                    start_left++;
                }
                else
                {
                    b[b_index] = source_array[start_right];
                    b_index++;
                    start_right++;
                }
            }

            // 4. 经过【3】步骤的合并，存在某个数组没有完全插入临时数组的情况
            // 当左数组未插完
            while (start_left <= end_left)
            {
                b[b_index] = source_array[start_left];
                b_index++;
                start_left++;
            }
            // 当右数组未插完
            while (start_right <= end_right)
            {
                b[b_index] = source_array[start_right];
                b_index++;
                start_right++;
            }       
        }

        // 每次两两分组合并后， 都需要将临时数组的值赋值回原数组。
        if (source_array != b)
        {
            for (int i = 0; i < source_array_length; i++)
            {
                source_array[i] = b[i];
            }
        }
    }
}


// 递归归并排序，从小到大
// 其中额外引入gap，初始值设为1
void merge_sort_recursive(int source_array[], int source_array_length, int gap)
{
    int start;
    int* b = (int*)malloc(source_array_length * sizeof(int));

    for (start = 0; start < source_array_length; start += gap * 2)
    {
        int b_index = start;

        int start_left = start;
        int end_left = start_left + gap - 1;

        int start_right = start + gap;
        int end_right = start_right + gap - 1;

        if (end_left >= source_array_length - 1)
        {
            for (; b_index < source_array_length; b_index++)
            {
                b[b_index] = source_array[b_index];
            }
            break;
        }

        if (end_right > source_array_length - 1)
        {
            end_right = source_array_length - 1;
        }

        while (start_left <= end_left && start_right <= end_right)
        {
            if (source_array[start_right] > source_array[start_left])
            {
                b[b_index] = source_array[start_left];
                b_index++;
                start_left++;
            }
            else
            {
                b[b_index] = source_array[start_right];
                b_index++;
                start_right++;
            }
        }

        while (start_left <= end_left)
        {
            b[b_index] = source_array[start_left];
            b_index++;
            start_left++;
        }
        while (start_right <= end_right)
        {
            b[b_index] = source_array[start_right];
            b_index++;
            start_right++;
        }
    }

    if (source_array != b)
    {
        for (int i = 0; i < source_array_length; i++)
        {
            source_array[i] = b[i];
        }
    }

    gap += gap;
    if (gap >= source_array_length)
    {
        return 0;
    }
    merge_sort_recursive(source_array, source_array_length, gap);

}


int* upset_array(int source_list[], int source_list_length)
{
    for (int i = 0; i < source_list_length; i++)
    {
        int rand_index = rand() % source_list_length;
        int tmp_value = source_list[i];
        source_list[i] = source_list[rand_index];
        source_list[rand_index] = tmp_value;
    }
    return source_list;
}


int main()
{
    // 生成随机测试列表
    int test_list[20];
    int test_list_length = sizeof(test_list) / sizeof(int);
    printf("测试列表： \n");
    for (int i = 0; i < test_list_length; i++)
    {
        test_list[i] = rand() % 100;
        printf("%d ", test_list[i]);
    }
    printf("\n");


    // 普通归并排序
    merge_sort_normal(test_list, test_list_length);
    printf("普通归并排序结果： \n");
    for (int i = 0; i < test_list_length; i++)
    {
        printf("%d ", test_list[i]);
    }
    printf("\n");


    // 打乱数组
    upset_array(test_list, test_list_length);
    printf("打乱测试列表： \n");
    for (int i = 0; i < test_list_length; i++)
    {
        printf("%d ", test_list[i]);
    }
    printf("\n");

    // 递归归并排序
    merge_sort_recursive(test_list, test_list_length, 1);
    printf("递归归并排序结果： \n");
    for (int i = 0; i < test_list_length; i++)
    {
        printf("%d ", test_list[i]);
    }
    printf("\n");


    return 0;
}

执行结果参考：

image.png