For any queries you can reach us at infovistarindia@gmail.com / WhatsApp us: +919158876092

Merge Sort in Data Structures - Infovistar

Merge Sort

Merge sort is the sorting algorithm that follows the divide and conquer technique. It is a popular and efficient sorting algorithm.

It splits the given list into two equal list i.e. sub-list. calls itself for the two lists and then merges the two sorted list.

The process of splitting and merging can be carried out recursively till there is only element in the list.

An array with single element is alway sorted.

Time Complexity

Case Time Complexity
Best Case O(n log n)
Average Case O(n log n)
Worst Case O(n log n)
  • Best Case O(n log n):It occurs when there is no sorting needed, i.e. the array is already sorted.
  • Average Case O(n log n): The array elements are in a jumbled order that is not properly ascending and descending.
  • Worst Case O(n log n): This occurs when the array elements need to be sorted in reverse order.

Space Complexity

Space Complexity O(n)
Stable Yes
  • A merge sort required extra variables for swapping. Hence, the space complexity of merge sorting is O(n).

Merge Sort

Advantages

  • It has a timing complexity of O (n log n).
  • It can be used for both internal and external sorting.
  • It is a stable sorting algorithm.

Disadvantages

  • It requires an additional memory for sorting of merged data during merging phase.