Understanding Merge Sort with Easy Example

If tutorials available on this website are helpful for you, please whitelist this website in your ad blocker😭 or Donate to help us ❤️ pay for the web hosting to keep the website running.

Merge Sort by Fotis Fotopoulos on Unsplash

Merge Sort क्या है?

Merge Sort एक algorithm है जो list या array को sort करता है। ये algorithm divide and conquer approach पर काम करता है।

Merge Sort एक algorithm है जो list या array को sort करता है। ये algorithm divide and conquer approach पर काम करता है।

Divide and Conquer Approach

• Divide : Array को छोटे sub-arrays में break करो।

• Conquer : हर sub-array को sort करो। 

• Combine : छोटे sorted arrays को merge करके एक sorted array बनाएं।
  

●●●

Merge Sort कैसे काम करता है?

अगर array का size 1 या 0 है, तो वो already sorted है। अगर array का size 2 या उससे ज़्यादा है, तो :

• उसको half में divide करो। 

• हर half को recursively merge sort apply करो। 

• जब दोनो halves sorted हो जाएँ , तब उनको merge करो।
  

Suppose आपका input array है :

[38, 27, 43, 3, 9, 82, 10]

Step 1: Divide

[38, 27, 43] and [3, 9, 82, 10]

Step 2: Further Divide

[38], [27, 43] → फिर [27], [43]
[3, 9], [82, 10] → फिर [3], [9] and [82], [10]

Step 3: Merge Sorted

[27, 43] → [27, 43]
[38, 27, 43] → [27, 38, 43]
[3, 9] → [3, 9], [10, 82] → [10, 82]
[3, 9, 10, 82]

Step 4: Final Merge

[27, 38, 43] and [3, 9, 10, 82] 

→ Final sorted array:
✅ [3, 9, 10, 27, 38, 43, 82]

●●●

Merge Sort Example

चलो अब एक simple example लेते हैं, जिसमे हम PHP में Merge Sort का implementation देखेंगे।

Copy
// Merge Sort Function
function mergeSort($array) {
    // Agar array ka size 1 ya 0 hai, toh return karo
    if(count($array) <= 1) {
        return $array;
    }

    // Array ko do halves mein divide karo
    $mid = floor(count($array) / 2);
    $left = array_slice($array, 0, $mid);
    $right = array_slice($array, $mid);

    // Recursively merge sort apply karo left aur right arrays par
    $left = mergeSort($left);
    $right = mergeSort($right);

    // Sorted left aur right arrays ko merge karo
    return merge($left, $right);
}

// Merge Function jo do arrays ko merge karega
function merge($left, $right) {
    $result = [];
    $i = 0;
    $j = 0;

    // Jab tak dono arrays mein elements hain
    while($i < count($left) && $j < count($right)) {
        if($left[$i] < $right[$j]) {
            $result[] = $left[$i];
            $i++;
        } else {
            $result[] = $right[$j];
            $j++;
        }
    }

    // Agar left array mein kuch elements bache hain
    while($i < count($left)) {
        $result[] = $left[$i];
        $i++;
    }

    // Agar right array mein kuch elements bache hain
    while($j < count($right)) {
        $result[] = $right[$j];
        $j++;
    }

    return $result;
}

// Example array
$array = [38, 27, 43, 3, 9, 82, 10];

// Merge Sort Apply karo
$sortedArray = mergeSort($array);

// Output the sorted array
echo "Sorted Array: ";
print_r($sortedArray);

Explanation of the Code

mergeSort function :

• ये function recursive है, अगर array के elements का size 1 या 0 है, तो वो array को directly return कर देता है, क्योंकि वो already sorted है।

• अगर array के elements ज़्यादा हैं, तो उससे दो sub-arrays में divide करते हैं और उन sub-arrays पर recursively merge sort apply करते हैं। 

• उसके बाद, दोनो sorted sub-arrays को merge function के through merge करते हैं।
  

merge function :

• ये function दो sorted arrays को merge करने का काम करता है।

• दो arrays के elements को compare करता है और smallest element को result array में add करता है। 

• जब एक array का traversal complete हो जाता है, दूसरे array के बाकी elements को result में directly add कर दिया जाता है।
  

●●●

Time Complexity of Merge Sort

Merge Sort कि time complexity O(n log n) होती है, जहाँ n array के elements कि count है। ये best case, average case, और worst case सभी conditions में same है, जो इस algorithm को काफी efficient बनाता है।

• Best Case: O(n log n)

• Average Case: O(n log n)

• Worst Case: O(n log n)

यह time complexity Merge Sort को Quick Sort से better बनाती है जब size बढ़ जाता है, क्योंकि Quick Sort कि worst case complexity O(n²) होती है।

●●●

Advantages of Merge Sort

1. Efficient Sorting : Merge Sort का time complexity O(n log n) है, जो किसी भी input size के लिए efficient है।

2. Stable Sorting : Merge Sort stable है, जो मतलब है कि अगर elements के अंदर कुछ similar values हैं, तो उनका relative order maintain रहेगा। 

3. Works on Linked Lists : Merge Sort को linked lists पर भी apply किया जा सकता है, जो कुछ और algorithms के लिए मुश्किल होता है।
   

Disadvantages of Merge Sort

1. Space Complexity: Merge Sort कि space complexity O(n) होती है, क्योंकि additional arrays बनाये जाते हैं sorting के लिए।

●●●

Conclusion

Merge Sort एक powerful sorting algorithm है जो efficiently large datasets को sort करने के लिए use होता है। इसका divide and conquer approach sorting को stable और efficient बनाता है।

I Hope , ऊपर दिए गए PHP example से आपको merge sort समझने में help मिली होगी। अगर आपको कोई और confusion हो तो comment section में पूछ सकते हैं।

Happy coding :)