Data Structure & Algorithm in Java

  1. Home
  2. Docs
  3. Data Structure & Alg...
  4. Sorting
  5. Merge Sort

Merge Sort

  • Merge sort is a sorting technique based on divide and conquer technique. With worst-case time complexity being Ο(n log n), it is one of the most used and approached algorithms.
  • It is one of the most popular and efficient sorting algorithm. It divides the given list into two equal halves, calls itself for the two halves and then merges the two sorted halves.
  • Merge sort is a divide-and-conquer algorithm based on the idea of breaking down a list into several sub-lists until each sub list consists of a single element and merging those sub lists in a manner that results into a sorted list.
  • Merge sort is a recursive algorithm that continuously splits the array in half until it cannot be further divided i.e., the array has only one element left (an array with one element is always sorted). Then the sorted subarrays are merged into one sorted array.
  • Sorting large datasets: Merge sort is particularly well-suited for sorting large datasets due to its guaranteed worst-case time complexity of O(n log n)
  • .External sorting: Merge sort is commonly used in external sorting, where the data to be sorted is too large to fit into memory.
  • Custom sorting: Merge sort can be adapted to handle different input distributions, such as partially sorted, nearly sorted, or completely unsorted data.
  • Stability: Merge sort is a stable sorting algorithm, which means it maintains the relative order of equal elements in the input array.
  • Guaranteed worst-case performance: Merge sort has a worst-case time complexity of O(N logN), which means it performs well even on large datasets.
  • Parallelizable: Merge sort is a naturally parallelizable algorithm, which means it can be easily parallelized to take advantage of multiple processors or threads.
  • Space complexity: Merge sort requires additional memory to store the merged sub-arrays during the sorting process. 
  • Not in-place: Merge sort is not an in-place sorting algorithm, which means it requires additional memory to store the sorted data. This can be a disadvantage in applications where memory usage is a concern.
  • Not always optimal for small datasets: For small datasets, Merge sort has a higher time complexity than some other sorting algorithms, such as insertion sort. This can result in slower performance for very small datasets.

To understand merge sort, we take an unsorted array as the following:


Step 4:

Now, combine them in the same manner they were broken.

image 29

Now, the array is completely sorted.

image 31

The space complexity of merge sort is O(n). It is because, in merge sort, an extra variable is required for swapping.

How can we help?

Leave a Reply

Your email address will not be published. Required fields are marked *