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.

Merge sort Algorithm

It works on below principle:

  • Divide list into sublist 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:

Merge sort implementation

I have printed intermediate steps to understand algorithm better.

MergeSortMain.java
When you run above program , you will get following output:
Array before sorting:
100 20 15 30 5 75 40
—————————–
Before Merging: 100 20
After merging: 20 100

Before Merging: 15 30
After merging: 15 30

Before Merging: 20 100 15 30
After merging: 15 20 30 100

Before Merging: 5 75
After merging: 5 75

Before Merging: 5 75 40
After merging: 5 40 75

Before Merging: 15 20 30 100 5 40 75
After merging: 5 15 20 30 40 75 100

—————————–
Array After sorting:
5 15 20 30 40 75 100

Time Complexity

Best case: O(nlogn)
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.

Was this post helpful?

Leave a Reply

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