How do I animate/draw a merge sort visualization?

Question

I want to animate the merge sort algorithm for my sorting visualizer, but the problem is that unlike some other algorithms, merge sort is recursive, so you constantly call the function from within the function by passing a segment of the original array. The problem appears when I try to draw it, because I cannot draw the smaller arrays, but I have to constantly update the original array. I am confused on what to do because to draw the process, I need the index of specific values that are valid for the original array, not the smaller ones. Does anyone have an idea or a solution?

Answer 1

You can achieve your goal by writing the mergesort passing the original array and index values to the slice being sorted.

Here is an example in javascript:

function merge(a, lo, m, hi) {
    var tmp = [];
    var len = m - lo;
    var i, j, k;
    // save left subarray
    for (i = 0; i < len; i++) {
        // animate this move
        tmp[i] = a[lo + i];
    }
    // merge subarrays
    i = 0;
    j = m;
    k = lo;
    while (i < len && j < hi) {
        if (tmp[i] <= a[j]) {
            // animate this move
            a[k++] = tmp[i++];
        } else {
            // animate this move
            a[k++] = a[j++];
        }
    }
    // copy the remaining elements
    while (i < len) {
        // animate this move
        a[k++] = tmp[i++];
    }
}

function mergesort(a, lo, hi) {
    if (hi - lo > 1) {
        var m = lo + ((hi - lo) >> 1);
        mergesort(a, lo, m);
        mergesort(a, m, hi);
        merge(a, lo, m, hi);
    }
}