- Algorithm merge-sort sorts a sequence S of size n in O(n log n) time, assuming two elements of S can be compared in O(1) time.
divide-and-conquer
- Divide: If the input size is smaller than a certain threshold, solve the problem directly and return. Otherwise, divide the input data into two or more disjoint subsets.
- Conquer: Recursively solve the subproblems associated with the subsets.
- Combine: Take the solutions to the subproblems and merge them into a solution to the original problem.
Array-Based Implementation of Merge-Sort
import java.util.Arrays;
import java.util.Comparator;
public class MergeSortArrayBased {
public static <K> void merge(K[] s1, K[] s2, K[] s, Comparator<K> comp) {
int i = 0, j = 0;
while (i + j < s.length) {
if (j == s2.length || (i < s1.length && comp.compare(s1[i], s2[j]) < 0))
s[i + j] = s1[i++];
else
s[i + j] = s2[j++];
}
}
public static <K> void mergeSort(K[] s, Comparator<K> comp) {
int n = s.length;
if (n < 2) return;
int mid = n / 2;
K[] s1 = Arrays.copyOfRange(s, 0, mid);
K[] s2 = Arrays.copyOfRange(s, mid, n);
mergeSort(s1, comp);
mergeSort(s2, comp);
merge(s1, s2, s, comp);
}
}
Sorting Linked Lists Based Merge Sort
import com.company.Queue.ArrayQueue;
import com.company.Queue.Queue;
import java.util.Comparator;
public class MergeSortLinkedQueueBased {
public static <K> void merge(Queue<K> s1, Queue<K> s2, Queue<K> s, Comparator<K> comp) {
while (!s1.isEmpty() && !s2.isEmpty()) {
if ( comp.compare(s1.first(), s2.first()) < 0)
s.enqueue(s1.dequeue());
else s.enqueue(s2.dequeue());
}
while (!s1.isEmpty())
s.enqueue(s1.dequeue());
while (!s2.isEmpty())
s.enqueue(s2.dequeue());
}
public static <K> void mergeSort(Queue<K> s, Comparator<K> comp) {
int n = s.size();
if (n < 2) return;
int mid = n / 2;
Queue<K> s1 = new ArrayQueue<>(mid);
Queue<K> s2 = new ArrayQueue<>(n - mid);
while (s1.size() < mid)
s1.enqueue(s.dequeue());
while (!s.isEmpty())
s2.enqueue(s.dequeue());
mergeSort(s1, comp);
mergeSort(s2, comp);
merge(s1, s2, s, comp);
}
}
A Bottom-Up (Nonrecursive) Array-Based Merge-Sort
- deploy a second array that stores the merged runs (swapping input and output arrays after each iteration).
```java
import java.util.Arrays;
import java.util.Comparator;
public class MergeSortNonRecursive {
public static
int end1 = Math.min(start + inc, in.length);
int end2 = Math.min(start + 2 * inc, in.length);
int x = start;
int y = start + inc;
int z = start;
while (x < end1 && y < end2) {
if (comp.compare(in[x], in[y]) < 0)
out[z++] = in[x++];
else out[z++] = in[y++];
}
while (x < end1)
out[z++] = in[x++];
while (y < end2)
out[z++] = in[y++];
}
public static <K> void mergeSortBottomUp(K[] orig, Comparator<K> comp) {
int n = orig.length;
K[] src = orig;
K[] dest= (K[]) new Object[n];
K[] temp;
for (int i = 1; i< n; i *= 2) {
for (int j = 0; j < n; j += i * 2) {
merge(src, dest, comp, j, i);
}
temp = src;
src = dest;
dest = temp;
}
if (orig != src)
System.arraycopy(src, 0, orig, 0, n);
} } ```
近期评论