Thread: Help to break a loop with time out

Hello again, here is the merge sort algorithm, the merge procedure is written iteratively but the main part of the function is recursive so I don't know where to put time tokens so as to control time of execution of the algorithm the same way as ones we have discussed.

Code:

void it_merge(int left, int middle, int right, ARRAY A){ /*In order to merge two sub arrays A1[l...m] & A[m+1...r]*/
    ARRAY TEMP;
    int i = left, j = middle + 1, k = 0;
    while(i <= middle && j <= right){
        if(A[i] <= A[j])
            TEMP[k++] = A[i++];
        else
            TEMP[k++] = A[j++];
    }
    while(i <= middle)
        TEMP[k++] = A[i++];
    while(j <= right)
        TEMP[k++] = A[j++];
    int c;
    for(c = 0; c < right-left+1; c++)
        A[left+c] = TEMP[c];
    }




void merge_sort_gen(int left, int right, ARRAY A){
    int middle;
    if(left < right){
        middle = (left + right) / 2;
        merge_sort_gen(left, middle, A);
        merge_sort_gen(middle + 1, right, A);
        it_merge(left, middle, right, A);
    }
}


void merge_sort(ARRAY A, int n){
    merge_sort_gen(0, n-1, A);
}

The first question is whether you really need to do it.
How long does the mergesort take when the size is 500000?
It can probably do that 20 times in less than 5 seconds.

Also remember that mergesort can be made faster by switching to an insertion or selection sort when the array is small (say 10 elements). And remember to compile with optimizations, too.

Here's one way of making it stop after MAX_TIME. Globals aren't strictly necessary, but I choose to use them.

Code:

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define SIZE 500000
#define MAX_TIME (3.0)  // short time for testing
#define SECONDS_SINCE(t) ((double)(clock() - (t)) / CLOCKS_PER_SEC)
#define MIN_SIZE_FOR_MERGESORT 11

// Hide globals in a struct for safety.
struct {
    int     cnt;
    clock_t start;
    double  total_time;
} global;
#define CHECK_EVERY_NTH 10  // Check time every nth recursive call.

void insertion_sort(int *a, int sz) {
    for (int n = 2; n <= sz; n++) {
        int x = a[n - 1], j;
        for (j = n - 2; j >= 0 && a[j] > x; j--)
            a[j + 1] = a[j];
        a[j + 1] = x;
    }
}

//merge two sub arrays A1[l...m] & A[m+1...r]
void merge(int left, int middle, int right, int *A){
    int TEMP[SIZE];
    int i = left, j = middle + 1, k = 0;
    while(i <= middle && j <= right){
        if(A[i] <= A[j])
            TEMP[k++] = A[i++];
        else
            TEMP[k++] = A[j++];
    }
    while(i <= middle)
        TEMP[k++] = A[i++];
    while(j <= right)
        TEMP[k++] = A[j++];
    for(i = 0; i < right-left+1; i++)
        A[left+i] = TEMP[i];
}

// Returns 0 to continue, 1 to quit due to too much time.
int merge_sort_gen(int left, int right, int *A) {
    if (left >= right) return 0;

    if (right - left <= MIN_SIZE_FOR_MERGESORT)
        insertion_sort(A + left, right - left + 1);
    else {
        int middle = (left + right) / 2;
        if (merge_sort_gen(left, middle, A))      // If it returns non-zero,
            return 1;                             // pass it up the call stack.
        if (merge_sort_gen(middle + 1, right, A)) // Ditto.
            return 1;
        merge(left, middle, right, A);
        if (++global.cnt % CHECK_EVERY_NTH == 0 &&
            SECONDS_SINCE(global.start) + global.total_time >= MAX_TIME)
            return 1; // Return non-zero to terminate the recursion.
    }
    return 0;
}

int merge_sort(int *A, int n){
    return merge_sort_gen(0, n-1, A);
}

int main() {
    int a[SIZE];
    srand(time(NULL));

    global.total_time = 0.0;
    for (;;) {
        for (int i = 0; i < SIZE; i++)
            a[i] = rand();
        global.cnt = 0;
        global.start = clock();
        if (merge_sort(a, SIZE)) {
            printf("time exceeded\n");
            break;
        }
        global.total_time += SECONDS_SINCE(global.start);
        printf("%lf\n", global.total_time);
    }

    return 0;
}