Strobes Strobes - 1 month ago 13
Java Question

Combining MergeSort with Insertion sort to make it more efficient

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(n2), 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.

Comments