C language recursive and non-recursive implementation source code and demo animation

C language recursive and non-recursive implementation source code and demo animation

//implementation 1
void merge_sort(int arr[], int len)
{
    int seg, start;
    int* a = arr, b = (int*) malloc(len * sizeof(int));
    
    for (seg = 1; seg < len; seg += seg) {
        for (start = 0; start < len; start += seg + seg) {
            int low = start, mid = min(start + seg, len), high = min(start + seg + seg, len);
            int k = low, start1 = low, end1 = mid, start2 = mid, end2 = high;
            while (start1 < end1 && start2 < end2) {
                b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
            }
            while (start1 < end1) {
                b[k++] = a[start1++];
            }
            while (start2 < end2) {
                b[k++] = a[start2++];
            }
        }
        int* tmp = a;
        a = b;
        b = tmp;
    }
    if (a != arr) {
        int i;
        for (i = 0; i < len; i++) {
            b[i] = a[i];
        }
        b = a;
    }
    free(b);
}

//implementation 2
void merge(int a[], int start, int mid, int end)
{
    int n1 = mid - start + 1;
    int n2 = end - mid;
    int left[n1], right[n2];
    int i, j, k;

    for (i = 0; i < n1; i++) {
        left[i] = a[start + i];
    }
    for (j = 0; j < n2; j++) {
        right[j] = a[mid + 1 + j];
    }

    i = j = 0;
    k = start;
    while (i < n1 && j < n2) {
        if (left[i] < right[j]) {
            a[k++] = left[i++];
        } else {
            a[k++] = right[j++];
        }
    }

    while (i < n1) {
        a[k++] = left[i++];
    }
    while (j < n2) {
        a[k++] = right[j++];
    }
}

void merge_sort(int a[], int start, int end)
{
    int mid;
    if (start < end) {
        mid = (start + end) / 2;
        merge_sort(a, start, mid);
        merge_sort(a, mid + 1, end);
        merge(a, start, mid, end);
    }
}

Demo animation





Comments

Popular posts from this blog

Python Receiving and parse JSON Data via UDP protocol

ubus lua client method and event registration code demo/example