DS Menu

Merge Sort

Merge Sort is a popular and efficient sorting algorithms. It works on the principle of Divide and Conquer strategy.

The fundamental operation in mergesort algorithm is merging two sorted lists. This is also known as two-way merge sort. Mergesort runs in O(n log n) worst-case running time, and the number of comparisons is nearly optimal. It is a good example of recursive algorithm.

We assume to sort the given array a[n] into ascending order. We split it into two subarrays: a[0]...a[n/2] and a[n/2)+1]...a[n-1]. Each subarray is individually sorted, and the resulting sorted subarrays are merged to produce a single sorted array of n elements. This is an ideal example of divide-and-conquer strategy. First, left half of the array a[0]...a[n/2] elements is being split and merged; and next second half of the array a[n/2)+1]...a[n-1] elements is processed Notice how the splitting continues until subarrays containing a single element are produce(d).

source from miro.medium.com

Here's a step-by-step explanation of the Merge Sort process

Divide: The array is divided into two halves (sub-arrays) recursively until each sub-array contains a single element. This is done by finding the middle of the array using the formula
$middle = \frac{(low + high)}{2}$
Conquer: Each pair of single-element sub-arrays is merged into a sorted array of two elements; these sorted arrays are then merged into sorted arrays of four elements, and so on.
Merge: Finally, all elements are merged into a single sorted array.

Pseudo-code

function mergeSort(arr, low, high)
    if low < high then
        mid = low + high / 2

        // Sort first and second halves
        mergeSort(arr, low, mid)
        mergeSort(arr, mid + 1, high)

        // Merge the sorted halves
        merge(arr, low, mid, high)

function merge(arr, low, mid, high)
    // Create temp arrays
	temp[low..high]
    i = low; j = mid+1; k = low
    
	while i < mid and j < high do
        if arr[i] <= arr[j] then
            temp[k] = arr[i]
            i++
        else
            temp[k] = arr[j]
            j++
        k++
    // Copy the remaining elements of Left sub array, if there are any
    while i < mid do
        temp[k] = arr[i]
        i++; k++
    // Copy the remaining elements of Right sub array, if there are any
    while j < high do
        temp[k] = arr[j]
        j++; k++ 
	
	//copying temp arrays back into arr[l..r]
	for i = low to high 
        arr[i] = temp[i]

Merge Sort Example

from wikipedia

Next Topic :Heap Sort