归并排序（MergeSort）是常见的排序算法，通过将排序问题分解为较小的子问题来进行排序

一：原理

将数组逐步拆分为较小的子数组，然后将这些子数组按顺序合并以获得最终的排序结果

二：步骤

1：将数组递归地拆分为两个子数组，直到每个子数组的长度为 0 或 1。

2：合并相邻的子数组，按顺序将它们合并为较大的有序子数组。

3：重复进行合并操作，直到所有子数组都合并为一个完整的有序数组

三：代码

const arr = [7, 2, 5, 1, 9, 3];

//第一步 拆分为小的子数组 [7, 2, 5], [1, 9, 3]
//第二步 递归继续拆 [7], [2], [5], [1], [9], [3]
//第三步 合并两个相邻子数组，按大小顺序 [7], [2] -> [2, 7] [5], [1] -> [1, 5]  [9], [3] -> [3, 9]
//第四步 重复性合并相邻数组，知道变成一个数组  [1, 2, 5, 7], [3, 9] -> [1, 2, 3, 5, 7, 9]

四：总结

1：时间复杂度是: O(n log n)

2：稳定的排序算法，需要额外的存储空间来存储临时数组

3：稳定性和时间复杂度的一致性更重要，可以选择归并排序