Question:
Which sorting algorithm has the best worst-case number of comparisons among comparison-based sorting algorithms, asymptotically achieving \(n \log_2 n – 1.44n\)?
तुलना-आधारित सॉर्टिंग एल्गोरिदम में किस एल्गोरिदम की तुलनाओं की सबसे खराब स्थिति की संख्या सबसे कम होती है, जो स्पर्शोन्मुख रूप से \(n \log_2 n – 1.44n\) प्राप्त करती है?
Options:
- Merge Sort
- Quick Sort
- Heap Sort
- Bubble Sort
- Merge Sort
- Quick Sort
- Heap Sort
- Bubble Sort
Correct Answer: a)
Explanation:
Merge Sort achieves the theoretical lower bound of comparison-based sorting with at most \(n \lceil \log_2 n \rceil – 2^{\lceil \log_2 n \rceil} + 1\) comparisons in the worst case.
मर्ज सॉर्ट (Merge Sort) सबसे खराब स्थिति में भी \(O(n \log n)\) तुलनाओं की गारंटी देता है जो तुलना-आधारित सॉर्टिंग की सैद्धांतिक न्यूनतम सीमा के सबसे करीब है।