What do you understand by Merge sort? Write the algorithm to sort using merge sort. Take an example to explain your answer.

Q.) What do you understand by Merge sort? Write the algorithm to sort using merge sort. Take an example to explain your answer.

 Subject: data structures

Merge Sort Algorithm

Merge sort is a sorting algorithm that is based on the principle of divide and conquer. It recursively divides the input array into smaller subarrays, sorts each subarray independently, and then merges the sorted subarrays back together to obtain the sorted array. The algorithm works as follows:

Divide:

  • Divide the array into two halves repeatedly until each subarray contains only one element.

Conquer:

  • Sort each subarray independently. This can be done using any sorting algorithm, but merge sort is typically used for this step due to its efficiency.

Merge:

  • Merge the sorted subarrays back together to obtain the sorted array. The merging process is done by comparing the elements of the two subarrays and placing the smaller element in the output array. This continues until all elements of both subarrays are merged.

Complexity Analysis:

  • Time Complexity:
    • Worst-Case Time Complexity: O(n log n)
    • Average-Case Time Complexity: O(n log n)
    • Best-Case Time Complexity: O(n) (when the array is already sorted)
  • Space Complexity: O(n) (for the temporary array used during merging)

Example:

To illustrate the merge sort algorithm, let's consider the following unsorted array:

[5, 3, 8, 2, 1, 4, 7, 6]

Step 1: Divide

  1. Divide the array into two halves:
   [5, 3, 8, 2]
   [1, 4, 7, 6]
  1. Continue dividing the subarrays into halves until each subarray contains only one element:
   [5] [3] [8] [2]
   [1] [4] [7] [6]

Step 2: Conquer

Sort each subarray independently. For simplicity, we will use the selection sort algorithm to sort each subarray:

[3, 5] [2, 8]
[1, 4] [6, 7]

Step 3: Merge

Merge the sorted subarrays back together to obtain the sorted array:

  1. Compare the first elements of each subarray and place the smaller element in the output array:
   [1, 3, 4, 5, 6, 7, 8, 2]
  1. Continue comparing and merging the elements until all elements of both subarrays are merged:
   [1, 2, 3, 4, 5, 6, 7, 8]

The final sorted array is:

[1, 2, 3, 4, 5, 6, 7, 8]

Conclusion

Merge sort is a powerful sorting algorithm that is efficient for sorting large arrays. It has a time complexity of O(n log n) in all cases and is relatively easy to implement.