In this article we are going to discuss one of the most important sorting algorithms: mergesort algorithm. Java programming language uses this method to sort objects. It has a guaranteed O(N logN) running time complexity. One disadvantage of mergesort is that it needs some extra memory. It is a divide and conquer algorithm.
First we have to divide the main problem into smaller subproblems. This is how divide and conquer algorithms work. So how to divide the problem as far as mergesort algorithm is concerned? We have an array of integers at the beginning. We split this array into two subarrays: left subarray and right subarray. Then we split these arrays as well until we have just a single item left in a subarray. Of course we consider an array with one element to be sorted by default.
We have the subarrays because of the divide phase. Now we have to merge these subarrays in order to end up with the sorted array. We have to consider two subarrays and have to merge them into another one. Thats why mergesort needs additional O(N) memory. We have to make sure we merge all the items from the left as well as from the right subarrays.
Let’s take a look at the concrete implementation of mergesort algorithm in Java!