you are here->home->Class 12->Merge Sort
Merge Sort

# The Procedure

## Real Lab Procedure

1. Define a function merge that takes four arguments "arr", "l", "m", "r":
• Compute the length of the two subarrays: "n1 = m - l + 1" and "n2 = r - m".
• Create two empty arrays "L" and "R" of length "n1" and "n2", respectively.
• Copy the left and right subarrays from "arr" into "L" and "R".
• Initialize variables "i", "j", and "k" to 0 and "l".
• Compare the first element of "L" and "R", and copy the smaller element to "arr[k]".
• Increment "i" or "j" depending on which element is copied.
• Increment "k".
• Repeat steps 5-7 until one of the subarrays is completely copied to "arr".
• Copy any remaining elements of the left or right subarray to "arr" if necessary.
2. Define a function mergeSort that takes three arguments "arr", "l", and "r":
1. If "l" is less than "r":
1. Compute the middle index "m".
2. Recursively call "mergeSort" on the left half of the array "arr[l:m]".
3. Recursively call "mergeSort" on the right half of the array "arr[m+1:r]".
4. Call merge function to merge the two sorted subarrays.
3. Call the "mergeSort" function with arguments "arr", "0", and "n-1".
4. Output the sorted array "arr".

## Simulator Procedure

1. Select the variables from the dropdown list.
2. Click on the Finish button or Start button to view the state diagram.
3. If you have clicked on the Start button then use Next and Previous button to view the State diagram.
4. Click on the Reset button when the State diagram is completed.