Jawaharlal Nehru Technological University Hyderabad MCA 2020 DATA STRUCTURES AND ALGORITHMS Previous Question Paper (October/ November - 2020 - R17)

Merge sort follows the divide and conquer paradigm by recursively splitting an array into halves until individual elements remain, then merging them in sorted order.

1. Divide: Find the midpoint m = (left + right) / 2.
2. Conquer: Recursively call MergeSort for the left subarray (left to m) and the right subarray (m + 1 to right).
3. Combine: Merge the two sorted subarrays into a single sorted array using a temporary array.

Algorithm MergeSort(A, left, right):

if left < right:
    mid = (left + right) / 2
    MergeSort(A, left, mid)
    MergeSort(A, mid + 1, right)
    Merge(A, left, mid, right)

To sort the list [20, 12, 14, 85, 94, 45, 74, 33, 25, 67], we divide recursively:

1. Split into [20, 12, 14, 85, 94] and [45, 74, 33, 25, 67].

2. Further split until single elements: [20], [12], [14], [85], [94], [45], [74], [33], [25], [67].

3. Merge pairs:

• [12, 20], [14, 85], [94], [45, 74], [25, 33], [67]
• [12, 14, 20, 85], [45, 94], [25, 33, 67, 74]
• [12, 14, 20, 45, 85, 94], [25, 33, 67, 74]
• Final Merge: [12, 14, 20, 25, 33, 45, 67, 74, 85, 94]

The sorted list is: 12, 14, 20, 25, 33, 45, 67, 74, 85, 94.