In sorting n items, merge sort has an average and worst-case performance of* O(n log n).In the worst case, merge sort does about 39% fewer comparisons* than quicksort does in the average case; merge sort always makes fewer* comparisons than quicksort, except in extremely rare cases, when they tie,* where merge sort’s worst case is found simultaneously with quicksort’s best* case. In terms of moves, merge sort’s worst case complexity is O(n log n)—the* same complexity as quicksort’s best case, and merge sort’s best case takes* about half as many iterations as the worst case.
Merge sort is often the best choice for sorting a linked list: in this* situation it is relatively easy to implement a merge sort in such a way that* it requires only O(1) extra space, and the slow random-access performance of* a linked list makes some other algorithms (such as quicksort) perform poorly,* and others (such as heapsort) completely impossible.
package com.sort.merge;
import java.util.Arrays;
public class MergeSort {
public int[] sort(int[] data) {
return recursiveSort(data, 0, data.length - 1);
}
public int[] recursiveSort(int[] data, int start, int end) {
if (start == end) {
return new int[] { data[start] };
}
int middle = (start + end) / 2;
return merge(recursiveSort(data, start, middle), recursiveSort(data,middle + 1, end));
}
public int[] merge(int[] a, int[] b) {
int[] result = new int[a.length + b.length];
int k = 0;
int j = 0;
for (int i = 0; i < result.length; i++) {
if (k == a.length || (j b[j])) {
result[i] = b[j];
j++;
} else {
result[i] = a[k];
k++;
}
}
System.out.println("result:" + Arrays.toString(result));
return result;
}
public static void main(String[] args) {
int[] data = new int[] { 15, 4, 42, 8, 23, 16};
System.out.println(Arrays.toString(new MergeSort().sort(data)));
}
