A9 Interview Question
abcsCountry: United States
Interview Type: In-Person
Merge sort can be inplace with O(n log n) and is stable.
#include <iostream>
using namespace std;
void print(int *a, int len) {
for (int i=0; i<len; i++)
cout << a[i];
cout << "\n";
}
void merge(int *a, int *b, int len1, int len2) {
int c[len1+len2];
int i=0, j=0, k=0;
while (i<len1 && j<len2) {
if (a[i] < b[j]) {
c[k++] = a[i++];
} else {
c[k++] = b[j++];
}
}
while (i<len1) {
c[k++] = a[i++];
}
while (j<len2) {
c[k++] = b[j++];
}
for(i=0; i<(len1+len2); i++) {
a[i] = c[i];
}
}
void sort(int *a, int start, int end) {
if (end <= start) return;
int len = end - start;
// ERROR: Must offset with index start to do inplace msort!
int mid = start + len/2;
if (len < 2) {
cout << "start " << start << ": " << a[start] << ", end " << end << ": " << a[end] << "\n";
if (a[start] > a[end]) {
int tmp = a[start];
a[start] = a[end];
a[end] = tmp;
}
} else {
cout << "start " << start << ": " << a[start] << ", mid " << mid << ": " << a[mid] << ", end " << end << ": " << a[end] << "\n";
sort(a, start, mid);
sort(a, mid+1, end);
merge(&a[start], &a[mid+1], (mid-start+1), (end-mid));
cout << "merge result: \n"; // << start << ": " << a[start] << ", mid " << mid << ": " << a[mid] << ," end " << end << ": " << a[end] << "\n";
print(&a[start], end-start + 1);
}
}
void msort(int *a, int len) {
sort(a, 0, len-1);
}
int main() {
int a[] = {3,2,1};
print(a, 3);
msort(a, 3);
print(a, 3);
int b[] = {9,0,1, 5, 2, 7, 2,3};
print(b, 8);
msort(b, 8);
print(b, 8);
return 0;
}
- AndroidFan June 26, 2016