/* Copy the remaining elements of L[], if there are any */
while (i < n1) { arr[k] = L[i]; i++; k++; }
我的代码是：
// Merge Sort Version
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <string.h>
void *memcpy(void *dest, const void *src, size_t n);
void merge(long arr[], long l, long m, long r) {
long i, j, k;
long n1 = m - l + 1;
long n2 = r - m;
/* create temp arrays */
long *L=malloc(sizeof(long)*n1);
long *R=malloc(sizeof(long)*n2);
/* Copy data to temp arrays L[] and R[] */
//for (i = 0; i < n1; i++) { L[i] = arr[l + i];}
memcpy(L, &arr[l], n1*sizeof(arr[l]));
//for (j = 0; j < n2; j++) { R[j] = arr[m + 1 + j];}
memcpy (R,&arr[m+1],n2*sizeof(arr[m+1]));
/* Merge the temp arrays back into arr[l..r]*/
i = 0; // Initial index of first subarray
j = 0; // Initial index of second subarray
k = l; // Initial index of merged subarray
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
/* Copy the remaining elements of L[], if there are any */
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
/* Copy the remaining elements of R[], if there are any */
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
/* l is for left index and r is right index of the sub-array of arr to be sorted */
void mergeSort(long *arr, long l, long r) {
if (l < r) {
// Same as (l+r)/2, but avoids overflow for large l and h
long m = l + (r - l) / 2;
// Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
void printArray(long A[], long size) {
for (long i = 0; i < size; i++)
printf("%ld ", A[i]);
printf("\n");
}
void randArray(long A[],long size){
for (long i = 0; i < size; i++)
A[i]=(rand()%10000);
}
/* Driver program to test above functions */
int main(int argc, char** argv) {
srand(time(0));//亂數要的
/********** Create and populate the array **********/
long n=2<<24;
n = atoi(argv[1]);
long *arr = malloc(n * sizeof(long));
srand(time(NULL));
/********** Initialize Array **********/
memset(arr,0,sizeof(n));
/********** Random generation **********/
randArray(arr,n);
long arr_size =n;
printf("This is the unsorted array:");
printArray(arr, arr_size);
//開始計時
double START, END;
START = clock();
mergeSort(arr, 0, arr_size - 1);
printf("This is the Sorted array:");
printArray(arr, arr_size);
END = clock();
printf("time is %.7f\n", (END - START) / CLOCKS_PER_SEC);
/********** Clean up rest **********/
free(arr);
return 0;
}
例如
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
memcpy(arr + k, L + i, (n1 - i) * sizeof(*arr));