admin管理员组文章数量:1596345
- Algorithm:
Goal. Given two sorted subarrays a[lo] to a[mid] and a[mid+1] to a[hi],
replace with sorted subarray a[lo] to a[hi].
public class Merge
{
private static void merge(...)
{ /* as before */ }
private static void sort(Comparable[] a, Comparable[] aux, int lo, int hi)
{
if (hi <= lo) return;
int mid = lo + (hi - lo) / 2;
sort(a, aux, lo, mid);
sort(a, aux, mid+1, hi);
merge(a, aux, lo, mid, hi);
}
public static void sort(Comparable[] a)
{
aux = new Comparable[a.length];
sort(a, aux, 0, a.length - 1);
}
}
Improvements:
1)Use insertion sort for small subarrays.
・Mergesort has too much overhead for tiny subarrays.
・Cutoff to insertion sort for ≈ 7 items.
2)Stop if already sorted.
・Is biggest item in first half ≤ smallest item in second half?
・Helps for partially-ordered arrays.
3)Eliminate the copy to the auxiliary array. Save time (but not space)
by switching the role of the input and auxiliary array in each recursive call.
- Complexity:
Proposition. Any compare-based sorting algorithm must use at least
lg ( N ! ) ~ N lg N compares in the worst-case.
- Bottom Up Mergesort:
- Stability:
Q. Which sorts are stable?
A. Insertion sort and mergesort (but not selection sort or shellsort).
本文标签: Mergesort
版权声明:本文标题:Mergesort 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dongtai/1728256540a1151083.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论