GATE CS 1995 Q1.5 — Searching, Sorting, Hashing

Merge Sort is a classic sorting algorithm based on the Divide and Conquer algorithmic paradigm.

The algorithm works recursively as follows:

1. Divide: Split the unsorted array of size $n$ into two halves of size approximately $n/2$.
2. Conquer: Recursively sort the two halves using merge sort.
3. Combine (Merge): Merge the two sorted halves back into a single sorted array.

Let's briefly review the other options:

• Backtracking approach: Used for solving constraint satisfaction problems (like the N-Queens problem) by exploring search paths and backing up when a path fails.
• Heuristic search: Used in artificial intelligence (like $A^*$ search) to find approximate solutions when exact algorithms are computationally expensive.
• Greedy approach: Makes locally optimal choices at each step with the hope of finding a global optimum (e.g., Kruskal's or Prim's algorithm).

Thus, the correct option is A.