Merge sort using ArrayList in Java with example

So here is another sorting algorithm, “Merge Sort” which I have implemented it using ArrayList.

MergeSort follows the Divide and Conquer paradigm.

Divide part divides an unsorted array into 2 unsorted arrays till further division is not possible i.e there is only 1 element per array. So we need to divide an array of N element into N arrays of size 1 (Virtually).

Conquer part join 2 divided arrays into one array which is sorted. So we need to merge element from N array to 1 array having all element in sorted order.

Diving the array will take O(log n) time and will create log n level of sub arrays.
Conquer part at each level will merge 2 sorted arrays which takes O(n) at each level.
So worst case time taken by merge sort is O(n log n).
Merge sort is not considered to be a memory efficient as we need an extra memory at each level of merging. As you can see in the implementation example that is given here it needs an extra temporary array called : mergedSortedArray to store the temp sorted element.

Here is the source code and project structure for the MergeSort.

Project Structure




You can have above code from GIT.


Leave a Reply

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