Technique: Merge Sort Animation

    Step by step animation. For the programming beginners to get a better understanding of merge sort.
    It is not easy to illustrate recursive using animation. The entire code flow in the animation is following its actual execution in the compiler, which might be a little different from the logic we usually mentioned in merge sort. I strongly recommend you test the code in your compiler to figure out how the recursive works.
    By clicking the snail, the animation starts, and by clicking it again, it goes back to the beginning.By clicking ">>" fast forward button, it can skip some stops. Probably, I will add a scroll bar later. The steps are kind of subtle, if there is any suggestion, please leave message to me and I will improve it.
 

 Cost: O(nlogn)
 Worst case: O(nlogn)
 Best case: O(nlogn) 
 Space cost: 2 * size of the element array
 Advantages: stable cost

Merge sort code in C++:

void Merge(int left, int mid, int right, int a[])

{

     int temp[50];                   

     int i = left;

     int j = mid+1;

     int index = 0;                                

     //merges the left part and the right part elements into a sorted list

     while (i <=mid && j <= right) {

              if (a[i] <= a[j]) {

                   temp[index] = a[i];

                   i++;

              }

              else {

                   temp[index] = a[j];

                   j++;

              }

              index++;

     }

     //copy the rest elements into temp array

     while (i <= mid) {

         temp[index] = a[i];

         i++;

         index++;

     }

     while (j <= right) {

         temp[index] = a[j];

         j++;

         index++;

     }

     //copy the sorted list back to original array

     for (int k = 0; k < index; k++) {

         a[k + left] = temp[k];

     }

}

void MergeSort(int left, int right, int a[])

{

     int mid;

     if(left<right)

     {

          mid = ((left + right) / 2);

          MergeSort(left, mid, a);

          MergeSort(mid+1, right, a);

          Merge(left, mid, right, a);

     }

}

 int main()

{

int a[]={25,49,8,25,21,16,32};

MergeSort(0,6,a);

}

More technique animations:

Quick Sort
Binary Search
Heap Sort 
Bubble Sort 
Selection Sort