Implement Merge sort in java

If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions.

Merge sort is divide and conquer sorting algorithm. It is efficient, comparison based sorting algorithm.

It works on below principle:

  • Divide list into sub list of about half size in each iteration until each sublist has only one element.
  • Merge each sublist repeatedly to create sorted list. It will run until we have only 1 sorted list. This will be the sorted list.
Below diagram will make it clearer:

Example of Merge sort:

I have printed intermediate steps to understand algorithm better.

MergeSortMain.java

When you run above program , you will get following output:

Complexity:

Best case: O(nlogn) or O(n)
Average case: O(nlogn)
Worst case: O(nlogn)
To understand more about complexity,please go through complexity of algorithm.

Please go through java interview programs for more such programs.

Add Comment