MERGE SORT IN DATA STRUCTURE

MERGE SORT:

 The process of merge sort is to divide the array into two halves, sort each half, and then 

merge the sorted halves back together. This process is repeated until the entire array is 

sorted. One of the main advantages of merge sort is that it has a time complexity of O(n 

log n), which means it can sort large arrays relatively quickly.

THE WORKING PROCESS OF MERGE SORT:

If the array has multiple elements, split the array into halves and recursively 

invoke the merge sort on each of the halves. Finally, when both halves are sorted, the 

merge operation is applied. Merge operation is the process of taking two smaller sorted

arrays and combining them to eventually make a larger one.

HOW DOES MERGE SORT WORKS?

Merge sort is a popular sorting algorithm known for its efficiency and stability. It follows the divide-and-conquer approach to sort a given array of elements.

Here’s a step-by-step explanation of how merge sort works:

1.Divide: Divide the list or array recursively into two halves until it can no more be divided.

2.Conquer: Each subarray is sorted individually using the merge sort algorithm.

3.Merge: The sorted subarrays are merged back together in sorted order. The process continues until all elements from both subarrays have been merged.

Illustration of Merge Sort:

Let’s sort the array or list [38, 27, 43, 10] using Merge Sort.

Let’s look at the working of above example:

DIVIDE:

[38, 27, 43, 10] is divided into [38, 27] and [43, 10].

[38, 27] is divided into [38] and [27].

[43, 10] is divided into [43] and [10].

CONQUER:

[38] is already sorted.

[27] is already sorted.

[43] is already sorted.

[10] is already sorted.

MERGE:

Merge [38] and [27] to get [27, 38].

Merge [43] and [10] to get [10,43].

Merge [27, 38] and [10,43] to get the final sorted list [10, 27, 38, 43]

THEREFORE,THE SORTED LIST IS [10,27,38,43].

DATA STRUCTURE