Sort with merge sort, and measure the work it really does.
What to build
A merge sort that counts the comparisons made between items.
Requirements
- Split a range at
mid = (lo + hi) / 2intolo .. midandmid + 1 .. hi. - Count one comparison each time the merge compares an item from the left with an item from the right.
- Print the sorted numbers and then the count.
Input
The first line has n. The second line has the n numbers.
Output
Two lines: the sorted numbers separated by spaces, and the number of comparisons.
Constraints
1 ≤ n ≤ 500.
Example
Input:
6
38 27 43 3 9 82
Output:
3 9 27 38 43 82
11
Why it works
The merge copies one item after each comparison, and stops comparing when one half runs out. So a merge of n items makes at most n − 1 comparisons, and merge sort never needs more than about n log₂ n in total.
Examples
Example 1 · Input
6 38 27 43 3 9 82
Expected output
3 9 27 38 43 82 11
Example 2 · Input
1 5
Expected output
5 0
Hints
Hint 1
Add 1 to a global counter every time the first `while` loop of the merge compares two items.
Hint 2
Do not count anything in the loops that copy the leftovers, since they compare no items.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int comparisons = 0;
int tmp[500];
void merge(int a[], int lo, int mid, int hi) {
int i = lo, j = mid + 1, k = 0;
while (i <= mid && j <= hi) {
comparisons++;
if (a[i] <= a[j]) tmp[k++] = a[i++];
else tmp[k++] = a[j++];
}
while (i <= mid) tmp[k++] = a[i++];
while (j <= hi) tmp[k++] = a[j++];
for (k = 0; k < hi - lo + 1; k++) a[lo + k] = tmp[k];
}
void merge_sort(int a[], int lo, int hi) {
if (lo >= hi) return;
int mid = (lo + hi) / 2;
merge_sort(a, lo, mid);
merge_sort(a, mid + 1, hi);
merge(a, lo, mid, hi);
}
int main(void) {
int n, a[500];
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
merge_sort(a, 0, n - 1);
for (int i = 0; i < n; i++) printf("%d ", a[i]);
printf("\n%d\n", comparisons);
return 0;
}