How to implement Merge Sort in java

Posted on Updated on

Merge sort is a divide and conquer algorithm which divide original data into smaller sets of data to solve the problem. In merge sort elements in the collection are divided into two part from middle which produce two collections into left and right parts. The resulting collections are again recursively splitted until they are broke into single element in the collection.

After split process, elements in each collection merge into third collection to produce sorted collection. To merge each elements, it picks the object which is smaller and inserts into new collection. For this collection it now selects the next elements and selects the smaller element from both collection by comparing one element from each collection at a time. This process is recursively done for all collections which were created during split process to produce sorted collection.

Performance of Merge Sort

  • Best Case performance          :    O(n log n) or O(n)
  • Average Case performance   :    O(n log n)
  • Worst Case performance       :    O(n log n)

Understand Merge Sort with an example.

mergesort

Let us see how this can be implemented in Java.

Output

Leave a Reply

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

Time limit is exhausted. Please reload CAPTCHA.