Merge sort

Merge sort

Merge sort is a sorting algorithm that follows the divide and conquers method. we use sorting techniques to rearrange a list of elements into a sorted list, either ascending or descending depending on the requirement. Java uses merge sort algorithm for array of objects. The default sorting is done in ascending order. We divide the elements into two halves, make the required steps for the two halves separately, and then we merge the two halves. The two halves are:

Divide: We divide the array into two halves and selected the middle element as out pivot element. We carry out this step till we divide the whole half array into little half arrays.

Conquer: We sort the halves of the array. We will then merge the divided arrays.

We can say merge sort is performed as merge(arr, a, m, r) that assumes arr(a,…m) and arr[m+1….r] are in the sorted form then merging two sorted set of elements into one set. For example, we have a list of elements:

23, 10, 62, 25

Step 1: we will divide the above set of 4 elements into 2. The first set becomes 23, 10 and second set becomes 62, 25

Step 2: First we check if the first half is sorted. It is not; therefore we swap both the elements. Now we get the first set as 10, 23

Step 3: Now we check if the second half is sorted or not. It is not; therefore we swap both the elements. Now we get the second set as 25, 62

When we merge both the sets using these 3 steps, we get the sorted list of elements as:

10, 23, 25, 62. 
It is a sorted set completely

Merge Sort Algorithm

  • Find middle point to divide the array into two.

Middle m = (a+r)/2

  • Call mergeSort for first half after division

Call mergeSort (arr, a, m)

  • It Calls mergeSort for second half

Call mergeSort (arr, m+1, r)

  • Merge the two halves sorted in step 2 and step 3.

Call mergeSort(arr, a, m, r)

Merge Sort Program in Java

package MyPackage;
public class DeveloperHelps{
void merge(int arr[], int beg, int mid, int end){
int l = mid - beg + 1;
int r = end - mid;
int LeftArray[] = new int [l];
int RightArray[] = new int [r];
for (int i=0; i<l; ++i)
LeftArray[i] = arr[beg + i];
for (int j=0; j<r; ++j)
RightArray[j] = arr[mid + 1+ j];
int i = 0, j = 0;
int k = beg;
while (i<l&&j<r){
if (LeftArray[i] <= RightArray[j]){
arr[k] = LeftArray[i];
i++;
}
else{
arr[k] = RightArray[j];
j++;
}
k++;
}
while (i<l){
arr[k] = LeftArray[i];
i++;
k++;
}
while (j<r)
{
arr[k] = RightArray[j];
j++;
k++;
}
}
void sort(int arr[], int beg, int end){
if (beg<end){
int mid = (beg+end)/2;
sort(arr, beg, mid);
sort(arr , mid+1, end);
merge(arr, beg, mid, end);
}
}
public static void main(String args[]){
int arr[] = {23,51,22,45,1,4,90,29,17,55};
DeveloperHelps ob = new DeveloperHelps();
ob.sort(arr, 0, arr.length-1);
System.out.println("Sorted array suing merge sort is");
for(int i =0; i<arr.length;i++){
System.out.println(arr[i]+"");}
}
}

The output of the above program is:

Sorted array suing merge sort is
1
4
17
22
23
29
45
51
55
90

Merge sort time complexity

  • We use it for sorting linked lists. Linked nodes may not be located adjacent in the memory in case of linked lists. We can insert extra elements in O(1) space in  O(1) time. Hence we can implement the sorting technique without using that extra space in the linked lists
  • We use the algorithm in the inversion count problem.
  • The algorithm can also be used in external sorting.

The time complexity is O(nLogn). In case of merge sort, the average, worst and best complexities are the same.  However, the space complexity in worst case scenario is O(n).

Leave a comment

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