MERGE SORT ALGORITHM

MERGE SORT ALGORITHM

Merge sort is one of the most efficient sorting methods based on split and split model. In merge sort, the problem is divided into two subtasks at each iteration. This greatly increases efficiency. . Follow the divide and conquer approach. The split continues until it splits the task into two subtasks and only one item in the quest set remains. “Capture” is basically concatenating 2 sorted arrays into the original array.

Merge sort uses a divide-and-conquer model. More specifically, it works as follows

1. Divide: Divide the array of n elements into two subarrays of n/2 elements each.

2. Conquer: Sort the two subarrays recursively using merge sort.

3. Combine: Merge the two sorted subarrays.

Merge sort implementation

When implementing the merge procedure, you can add the special value ∞ to avoid checking that each subarray is empty. Whenever the pointer of one subarray is moved to ∞ , all values ​​in the remaining subarray are sequentially placed into the output array until that subarray is empty because all values ​​in the remaining subarray are less than ∞ .

Time Complexity of Merge sort

Worst case, at each iteration, split the problem into 2 subtasks. So this takes log n operations and has to be done for n iterations, resulting in a total of n log n operations. : If it’s a sorted array at best, you can use a flag to make some modifications to check whether the weep is already sorted.

Best Time Complexity: O(nlogn)

Average Time Complexity: O(nlogn)

Worst Time Complexity: O(nlogn)

This article introduced merge sort algorithm, O(NlongN) time and exact sort algorithm. Merge sort uses divide and conquer method.