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++:
Binary Search
Heap Sort
Bubble Sort
Selection 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 SortMore technique animations:
Binary Search
Heap Sort
Bubble Sort
Selection Sort
