```
🔀 MERGE SORT VISUALIZER
Divide • Conquer • Merge • Step-by-Step Animation
```
```
📥 Enter Your Data
```
```
📊 Current Array
Enter values and press START SORT.
```
```
```
📈 Live Statistics
Current Level
0
Comparisons
0
Merges
0
Current Step
0
Array Size
0
```
🌳 Divide Structure
```
```
```
📝 Step-by-Step Explanation
1
Merge Sort follows the
Divide and Conquer
strategy. The array is repeatedly divided
into smaller parts until every part contains
one element.
```
🧮 Merge Sort Mathematics
Divide the array:
mid = ⌊(low + high) / 2⌋
Left part:
A[low ... mid]
Right part:
A[mid+1 ... high]
Then merge the two sorted parts by repeatedly selecting the smaller front element.
```
mid = ⌊(low + high) / 2⌋
Left part:
A[low ... mid]
Right part:
A[mid+1 ... high]
Then merge the two sorted parts by repeatedly selecting the smaller front element.
```
🔢 Complete Mathematical Example
Initial Array:
38, 27, 43, 3
Calculate midpoint:
mid = (0 + 3) / 2 = 1
Divide:
Left = 38, 27
Right = 43, 3
Divide again:
[38,27] → [38] [27]
[43,3] → [43] [3]
Merge [38] and [27]:
27 < 38
Result: [27,38]
Merge [43] and [3]:
3 < 43
Result: [3,43]
Final Merge:
Compare 27 and 3 → choose 3
Compare 27 and 43 → choose 27
Compare 38 and 43 → choose 38
Remaining element → 43
Final Result:
3, 27, 38, 43
```
38, 27, 43, 3
Calculate midpoint:
mid = (0 + 3) / 2 = 1
Divide:
Left = 38, 27
Right = 43, 3
Divide again:
[38,27] → [38] [27]
[43,3] → [43] [3]
Merge [38] and [27]:
27 < 38
Result: [27,38]
Merge [43] and [3]:
3 < 43
Result: [3,43]
Final Merge:
Compare 27 and 3 → choose 3
Compare 27 and 43 → choose 27
Compare 38 and 43 → choose 38
Remaining element → 43
Final Result:
3, 27, 38, 43
```
```
💡 How Merge Sort Works
1
Divide:
Split the array into two approximately equal parts.
2
Continue dividing each part until every subarray
contains only one element.
3
A single element is already considered sorted.
4
Merge:
Compare the front elements of two sorted subarrays.
5
Copy the smaller element into the result.
6
Continue until both subarrays have been completely merged.
```
```
⚖️ Advantages & Disadvantages
+
Advantages
• Guaranteed O(n log n) time complexity.
• Very effective for large datasets.
• Stable sorting algorithm.
• Works particularly well with linked lists and external sorting.
• Guaranteed O(n log n) time complexity.
• Very effective for large datasets.
• Stable sorting algorithm.
• Works particularly well with linked lists and external sorting.
−
Disadvantages
• Requires additional memory for merging.
• More complicated than Bubble Sort.
• For small arrays, simpler algorithms can sometimes be preferable.
• Requires additional memory for merging.
• More complicated than Bubble Sort.
• For small arrays, simpler algorithms can sometimes be preferable.
```
```
⏱️ Time & Space Complexity
Best Case
O(n log n)
Average Case
O(n log n)
Worst Case
O(n log n)
Extra Space
O(n)
No comments:
Post a Comment