编写程序：对包含 N 个数字的数组执行归并排序（Merge Sort）。

Write a program to perform Merge Sort on an array of N numbers.

题目类型: 技术面试题

这是一道技术面试题，常见于澳洲IT公司面试中。

难度: medium

分类: Algorithms, Coding, DSA

标签: merge sort, divide and conquer

参考答案摘要

答案 归并排序使用 分治 ：把数组递归拆成两半分别排序，再用双指针把两个有序子数组合并。它在最坏/平均情况下都为 O(N log N) ，稳定排序；但需要额外临时数组，空间复杂度通常为 O(N) 。 // Java (core idea) void mergeSort(int[] a, int l, int r){ if(l>=r) return; int m = l + (r-l)/2; mer...

本题提供 STAR 原则详细解答和技术解析，登录匠人学院学习中心即可查看完整答案。