62 lines
1.2 KiB
C
62 lines
1.2 KiB
C
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#define Array int *
|
|
|
|
Array readArray(int *size) {
|
|
int d, i = 0;
|
|
char c;
|
|
Array A;
|
|
|
|
*size = 1;
|
|
A = malloc(sizeof(int));
|
|
do {
|
|
if (!scanf(" %d", &d))
|
|
continue;
|
|
if (i == *size - 1) {
|
|
*size *= 2;
|
|
A = realloc(A, *size * sizeof(int));
|
|
}
|
|
A[i++] = d;
|
|
} while ((c = getchar()) != EOF && c != '\n');
|
|
*size = i;
|
|
return A;
|
|
}
|
|
|
|
void interleave(Array A, int pivot, int size) {
|
|
int i, tmp = A[pivot];
|
|
|
|
if (pivot == size)
|
|
return;
|
|
for (i = pivot; i > 0 && A[i - 1] > tmp; i--)
|
|
A[i] = A[i - 1];
|
|
A[i] = tmp;
|
|
interleave(A, pivot + 1, size);
|
|
}
|
|
|
|
void mergeSort(Array A, int size) {
|
|
int pivot;
|
|
|
|
if (size <= 1)
|
|
return;
|
|
pivot = size / 2;
|
|
mergeSort(A, pivot);
|
|
mergeSort(A + pivot, size - pivot);
|
|
interleave(A, pivot, size);
|
|
}
|
|
|
|
int main() {
|
|
Array A;
|
|
int i, size;
|
|
|
|
printf("This program performs an in-place merge sort.\nType in a sequence "
|
|
"of values separated by spaces and press ENTER: ");
|
|
A = readArray(&size);
|
|
mergeSort(A, size);
|
|
|
|
printf("New sequence:\n");
|
|
for (i = 0; i < size; i++)
|
|
printf("%d ", A[i]);
|
|
printf("\n");
|
|
return 0;
|
|
}
|