\
home Home
sort Sorts
Bubble Sort Selection Sort Insertion Sort Quick Sort Randomized Quick Heap Sort Counting Sort Gnome Sort Stooge Sort
SORTING VISUALIZER - MERGE SORT

  MergeSort(A[],p,r)

    1.   If p < r

    2.     q = (p+r)/2

    3.     MergeSort(A, p, q)

    4.     MergeSort(A, q+1, r)

    5.     Merge(A, p, q, r)

        1.   n1 = q-p+1 & n2 = r-q

        2.   create L[1..n1], R[1..n2]

        3.   i =0 & j = 0

        4.   while i< n1 & j< n2

        5.     If L[i]<= R[i]

        6.     A[i] <- L[i]

        7.     i++

        8.     Else:

        9.     A[i] <- R[i]

        10.     i++

        11.   while i< n1

        12.     A[i] <- L[i]

        13.     i++

        14.   while j< n2

        15     A[i] <- R[i]

        16.     j++

    6.   End If

No of Comparisons:

   
         

Complexity

Time
 Space
Best Case Average Case Worst Case
O(n)
O(nlog(n))
O(nlog(n))
O(nlog(n))

Merge Sort

What is the working mechanism of Merge Sort ?

Merge sort is a divide-and-conquer algorithm that works by dividing an array into two halves, sorting each half separately, and then merging them back together.


Is Merge sort a stable, in-place sorting algorithm or an out-of-place sorting algorithm?

Merge sort is an out-of-place sorting algorithm. It requires additional memory space to store the subarrays being merged during the sorting process. It is Stable.


How does the number of elements impact the efficiency of Merge sort?

The time complexity of merge sort is O(n log n), where n is the number of elements in the array. When number of elements is small it may not be better than other algos such as insertion sort but when no. of elements INCREASES it becomes MORE EFFICIENT as compared to others as it's time complexity grows slower then other algorithms.


What are advantages and disadvantages of Merge Sort?

Advantages:

  • Merge sort provides a consistent performance, as it always has a time complexity of O(n*log(n)).
  • It is stable that means order of the elements is maintained.
  • works efficiently on a wide range of input data types, including arrays, linked lists, and other data structures.
  • It cam handle large inputs in a reasonable amount of time.

    • Disadvantages:
    • Merge sort requires extra space to hold the temporary arrays during the merging process.
    • Merge sort is a recursive algorithm. Therefore, require a lot of function calls and memory management.