मर्ज सॉर्ट (Merge Sort)
डिवाइड-एंड-कॉन्कर एल्गोरिदम: ऐरे को आधा-आधा विभाजित करें जब तक सिंगल एलिमेंट्स न रह जाएं, फिर सॉर्टेड मर्ज करें। समय जटिलता: O(n log n) (सभी केसेस में)।
एल्गोरिदम चरण
- विभाजन: ऐरे को दो भागों में बांटें, पुनरावर्ती रूप से जारी रखें
- विजय: सिंगल-एलिमेंट ऐरे पहले से सॉर्टेड हैं
- मर्ज: दो सॉर्टेड ऐरे को मर्ज करें
उदाहरण: [4,7,5,9,1,3,8,2]
विभाजन: [4,7,5,9] [1,3,8,2]
[4,7] [5,9] [1,3] [8,2]
[4][7] [5][9] [1][3] [8][2]
मर्ज: [4,7] [5,9] [1,3] [2,8]
[4,5,7,9] [1,2,3,8]
[1,2,3,4,5,7,8,9] ← फाइनल
इम्प्लीमेंटेशन
<html> <body> <script>
function mergeSort(array) {
// बेस केस: सिंगल एलिमेंट या खाली
if (array.length <= 1) return array;
// विभाजन
const mid = Math.floor(array.length / 2);
const left = array.slice(0, mid);
const right = array.slice(mid);
// पुनरावर्ती कॉल + मर्ज
return merge(mergeSort(left), mergeSort(right));
}
// दो सॉर्टेड ऐरे मर्ज करें
function merge(left, right) {
let result = [];
let leftIndex = 0;
let rightIndex = 0;
// दोनों में छोटा चुनें
while (leftIndex < left.length && rightIndex < right.length) {
if (left[leftIndex] < right[rightIndex]) {
result.push(left[leftIndex]);
leftIndex++;
} else {
result.push(right[rightIndex]);
rightIndex++;
}
}
// शेष एलिमेंट्स जोड़ें
return result
.concat(left.slice(leftIndex))
.concat(right.slice(rightIndex));
}
const list = [4, 7, 5, 9, 1, 3, 8, 2];
document.write("मूल: " + list + "<br>");
document.write("सॉर्टेड: " + mergeSort(list));
</script> </body> </html>
आउटपुट
मूल: 4,7,5,9,1,3,8,2 सॉर्टेड: 1,2,3,4,5,7,8,9
विशेषताएं
| पहलू | विवरण |
|---|---|
| समय जटिलता | O(n log n) - बेस्ट, एवरेज, वर्स्ट |
| स्पेस जटिलता | O(n) - सहायक ऐरे |
| स्थिर (Stable) | हाँ - समान एलिमेंट्स का क्रम बरकरार |
| इन-प्लेस | नहीं (आमतौर पर) |
उपयोग के मामले
- लिंक्ड लिस्ट्स सॉर्टिंग (O(1) स्पेस संभव)
- एक्सटर्नल सॉर्टिंग (बड़ी फाइल्स)
- जब स्टेबल सॉर्ट चाहिए
- फंक्शनल प्रोग्रामिंग (इम्म्यूटेबल डेटा)
JavaScript बिल्ट-इन
<script> // प्रोडक्शन में बिल्ट-इन उपयोग करें (हाइली ऑप्टिमाइज़्ड) var arr = [4, 7, 5, 9, 1, 3, 8, 2]; arr.sort((a, b) => a - b); // [1, 2, 3, 4, 5, 7, 8, 9] </script>