Strobes - 3 months ago 22

Java Question

So I have a MergeSort algorithm and I want to combine MergeSort with Insertion sort to reduce the overhead of merging, the question is how? I want to sort the segments using insertion sort and then merge.

`public class mergesorttest{`

public static void main(String[]args){

int d[]= {10,2,3,4,5,6,5,4,3,5,6,7,1};

mergeSort(d,0,d.length);

for(int x:d) System.out.print(x+" ");

System.out.println();

}

static void mergeSort(int f[],int lb, int ub){

//termination reached when a segment of size 1 reached -lb+1=ub

if(lb+1<ub){

int mid = (lb+ub)/2;

mergeSort(f,lb,mid);

mergeSort(f,mid,ub);

merge(f,lb,mid,ub);

}

}

static void merge (int f[],int p, int q, int r){

//p<=q<=r

int i =p; int j = q;

//use temp array to store merged sub-sequence

int temp[] = new int[r-p]; int t = 0;

while(i<q && j<r){

if(f[i]<=f[j]){

temp[t] =f[i];

i++;t++;

}

else{

temp[t] = f[j];

j++;

t++;

}

//tag on remaining sequence

while(i<q){

temp[t] = f[i];

i++;

t++;

}

while(j<r){

temp[t]=f[j];

j++;

t++;

}

//copy temp back to f

i=p;t=0;

while(t<temp.length){

f[i]=temp[t];

i++;

t++;

}

}

}

}

`public static void insertion_srt(int array[], int n, int b){`

for (int i = 1; i < n; i++){

int j = i;

int B = array[i];

while ((j > 0) && (array[j-1] > B)){

array[j] = array[j-1];

j--;

}

array[j] = B;

}

}

Answer

The merging automatically takes care of sorting the elements. However, one can sort using insertion sort when the list gets below some threshold:

```
static final int THRESHOLD = 10;
static void mergeSort(int f[],int lb, int ub){
if (ub - lb <= THRESHOLD)
insertionSort(f, lb, ub);
else
{
int mid = (lb+ub)/2;
mergeSort(f,lb,mid);
mergeSort(f,mid,ub);
merge(f,lb,mid,ub);
}
}
```

Doing anything other than this (except playing around with the threshold a little) will **increase** the time taken by merge sort.

Although merge sort is O(n log n) and insertion sort is O(n^{2}), insertion sort has better constants and is thus faster on very small arrays. This, this, this and this are a few related questions I found.