Merge Sort in Java using Divide and Conquer

Merge sort is a divide and conquer algorithm. The sorting elements are stored in a collection. This collection is divided into two collections and these are again sorted via mergesort.

Once the two collections are sorted then the result is combined .Merge sort will take the middle of the collection and takes then the two collection for the next iteration of mergesort. In the merging part mergesort runs through the both collections and selects the lowest of the both to insert it into a new collection.

In comparison to quicksort the divide part is simple in mergesort while the merging take is complex. In addition quicksort can work "inline", e.g. it does not have to create a copy of the collection while mergesort requires a copy.

Wikipedia

Algorithm :

1. Divide the unsorted list into n sublists, each containing 1 element (a list of 1 element is considered sorted).
2. Repeatedly Merge sub lists to produce new sublists until there is only 1 sublist remaining. (This will be the sorted list.)

Merge Sort

When you run the program, the output will be:

Before Sort

Contents of the Array : 30 | 36 | 67 | 56 | 76 | 29 | 12 | 49 | 56 | 75 | 16 | 92 | 34 | 95 | 44 | 

After Sort

Contents of the Array : 12 | 16 | 29 | 30 | 34 | 36 | 44 | 49 | 56 | 56 | 67 | 75 | 76 | 92 | 95 |