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.

Related Posts

  • 04 November

    Topological Sort in java

    In this post, we will see about Topological Sorting in the graph. Topological Sorting is ordering of vertices or nodes such if there is an edge between (u,v) then u should come before v in topological sorting. Topological sort is possible only for Directed Acyclic Graph(DAG). If there is a cycle in graph, then there […]

  • 23 August

    Sort array in java

    In this post, we will see how to sort an array in java. There are various ways to sort array in java. You can implement different sorting algorithms to sort an array. You can use Arrays.sort method to sort array in java. There are various overloaded versions of Arrays.sort method. You can go through it […]

  • 12 October

    Selection sort in java

    If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview programs. Selection sort is an in place comparison sorting algorithm. It is very simple to implement but it does not go well with large number of inputs. Selection sort algorithm Find the minimum element in the list. […]

  • 12 October

    Shell sort in java

    Shell sort is in place comparison based sorting algorithm. It is generalization of insertion sort. It was invented by Donald shell. It allows to sort elements which are far apart. In case of insertion sort, comparison happens between only adjacent elements but in shell sort, it avoid comparing adjacent elements until last steps. Last step of shell […]

  • 12 October

    Quick Sort in java

    If you want to practice data structure and algorithm programs, you can go through data structure and algorithm interview questions. Quick sort or partition-exchange sort, is a sorting algorithm, which is using divide and conquer algorithm. In quick sort, we first choose a pivot and divide into two sublists,one will contain elements lower than pivot and […]

  • 12 October

    Counting Sort in java

    Counting sort is special sorting technique used to sort elements between specific range. Lets say elements belong to range 1 to K , then Counting sort can be used to sort elements in O(N) times. Basic idea of counting sort to find number of elements less than X, so X can be put to its […]

Leave a Reply

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

Subscribe to our newletter

Get quality tutorials to your inbox. Subscribe now.