Java – algorithm: mixed mergesort and insertionsort execution time
Good day, so community,
I am a CS student and am currently conducting an experiment combining mergesort and insertionsort Understandably, for a certain threshold, s, insertionsort will have faster execution time than mergesort Therefore, by combining the two sorting algorithms, the total running time will be optimized
However, after running the experiment for many times, using 1000 sample sizes and different sizes of S, the experimental results do not give a definite answer every time This is a picture of a better result (please note that half the time of the result is not certain):
Now try the same algorithm code with a sample size of 3500:
Finally, try the same algorithm code with a sample size of 500000 (note that the y-axis is in milliseconds:
Although logically, when s < = 10, hybrid mergesort will be faster, because insertionsort has no recursive overhead time However, the results of my mini experiment say otherwise At present, these are the time complexity taught me: mergesort: O (n log n) insertion sort: > best case: θ (n) > worst case: θ (n ^ 2)
Finally, I found an online source: https://cs.stackexchange.com/questions/68179/combining-merge-sort-and-insertion-sort , which states:
Hybrid MergeInsertionSort：
>Best case: θ (n log (n / x)) > worst case: θ (nx n log(n / x))
I would like to ask whether there is any evidence in the CS community that the results show that the hybrid mergesort algorithm is better than the normal mergesort algorithm below a certain threshold S. if so, why?
Thank you so much to the so community. This may be a trivial question, but it will certainly clarify many of my current questions about time complexity and things:)
Note: I use java to write algorithms. The runtime may be affected by the way Java stores data in memory
Code in Java:
public static int mergeSort2(int n,int m,int s,int[] arr){
int mid = (n+m)/2,right=0,left=0;
if(m-n<=s)
return insertSort(arr,n,m);
else
{
right = mergeSort2(n,mid,s,arr);
left = mergeSort2(mid+1,m,arr);
return right+left+merge(n,arr);
}
}
public static int insertSort(int[] arr,int n,int m){
int temp,comp=0;
for(int i=n+1; i<= m; i++){
for(int j=i; j>n; j--){
comp++;
comparison2++;
if(arr[j]<arr[j-1]){
temp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = temp;
}
else
break;
}
}
return comp;
}
public static void shiftArr(int start,int[] arr){
for(int i=m; i>start; i--)
arr[i] = arr[i-1];
}
public static int merge(int n,int[] arr){
int comp=0;
if(m-n<=s)
return 0;
int mid = (n+m)/2;
int temp,i=n,j=mid+1;
while(i<=mid && j<=m)
{
comp++;
comparison2++;
if(arr[i] >= arr[j])
{
if(i==mid++&&j==m && (arr[i]==arr[j]))
break;
temp = arr[j];
shiftArr(i,j++,arr);
arr[i] = temp;
if(arr[i+1]==arr[i]){
i++;
}
}
i++;
}
return comp;
}
Solution
The sample code is not a traditional merge sort The merge function is moving the array instead of merging between the original array and the temporary working array
I tested top-down and bottom-up merge sorting, and both took about 42 milliseconds = = 0.042 seconds to sort 500000 32-bit integers, while the obvious result in the chart was 1000 times slower at about 42 seconds instead of 42 milliseconds I also tested 10000000 integers, which took more than a second to sort
In the past, using C, I compared the bottom-up merge sort with the mixed bottom-up merge / insert sort. For 16 million (2 ^ 24 = = 16777216) 32-bit integers, the mixed sort is about 8% faster than s = = 16 S = = 64 is slightly slower than s = = 16 Visual Studio std :: stable_ Sort is a variant of bottom-up merge sort (the temporary array is 1 / 2 the size of the original array) and insert sort, and uses S = = 32
For small arrays, insert sort is faster than merge sort, which is a combination of cache locality and fewer instructions required to sort small arrays using insert sort For pseudorandom data and S = = 16 to 64, insert sort is about twice as fast as merge sort
The relative gain decreases with the increase of array size Considering the influence of bottom-up merge sorting, only 4 merge passes are optimized when s = = 16 In my test case, there are 2 ^ 24 = = 16216 elements, i.e. 4 / 24 = 1 / 6 ~ = 16.7% of the number of passes, resulting in an improvement of about 8% (so the insertion sort is about twice the combined sort) and waiting for 4 passes) The total time of merge sort only is about 1.52 seconds, the total time of hybrid sort is about 1.40 seconds, and the gain is 0.12 seconds for the process requiring only 1.52 seconds For top - down merge sort, s = = 16, the 4 deepest recursions will be optimized
Update – sample java code for hybrid in place merge sort / insert sort with O (n log (n)) time complexity (note – secondary storage is still consumed on the stack due to recursion.) The local part is completed by exchanging the data in the merge area and the data in the merge area during the merge step This is not a stable sort (the order of equal elements is not preserved due to the exchange in the merge step) Sorting 500000 integers takes about 1 / 8 second, so I increase it to 16 million (2 ^ 24 = = 16777216) integers, which takes a little more than 4 seconds If there is no insertion sort, the sort takes about 4.524 seconds, while using the insertion sort with S = = 64, the sort takes about 4.150 seconds and the gain is about 8.8% The same code is basically used in C with less improvement: from 2.88 seconds to 2.75 seconds, the gain is about 4.5%
package msortih;
import java.util.Random;
public class msortih {
static final int S = 64; // use insertion sort if size <= S
static void swap(int[] a,int i,int j) {
int tmp = a[i]; a[i] = a[j]; a[j] = tmp;
}
// a[w:] = merged a[i:m]+a[j:n]
// a[i:] = reordered a[w:]
static void wmerge(int[] a,int j,int w) {
while (i < m && j < n)
swap(a,w++,a[i] < a[j] ? i++ : j++);
while (i < m)
swap(a,i++);
while (j < n)
swap(a,j++);
}
// a[w:] = sorted a[b:e]
// a[b:e] = reordered a[w:]
static void wsort(int[] a,int b,int e,int w) {
int m;
if (e - b > 1) {
m = b + (e - b) / 2;
imsort(a,b,m);
imsort(a,e);
wmerge(a,e,w);
}
else
while (b < e)
swap(a,b++,w++);
}
// inplace merge sort a[b:e]
static void imsort(int[] a,int e) {
int m,w,x;
int t;
// if <= S elements,use insertion sort
if (e - b <= S){
for(n = b+1; n < e; n++){
t = a[n];
m = n-1;
while(m >= b && a[m] > t){
a[m+1] = a[m];
m--;}
a[m+1] = t;}
return;
}
if (e - b > 1) {
// split a[b:e]
m = b + (e - b) / 2;
w = b + e - m;
// wsort -> a[w:e] = sorted a[b:m]
// a[b:m] = reordered a[w:e]
wsort(a,w);
while (w - b > 2) {
// split a[b:w],w = new mid point
n = w;
w = b + (n - b + 1) / 2;
x = b + n - w;
// wsort -> a[b:x] = sorted a[w:n]
// a[w:n] = reordered a[b:x]
wsort(a,b);
// wmerge -> a[w:e] = merged a[b:x]+a[n:e]
// a[b:x] = reordered a[w:n]
wmerge(a,x,w);
}
// insert a[b:w] into a[b:e] using left shift
for (n = w; n > b; --n) {
t = a[n-1];
for (m = n; m < e && a[m] < t; ++m)
a[m-1] = a[m];
a[m-1] = t;
}
}
}
public static void main(String[] args) {
int[] a = new int[16*1024*1024];
Random r = new Random(0);
for(int i = 0; i < a.length; i++)
a[i] = r.nextInt();
long bgn,end;
bgn = System.currentTimeMillis();
imsort(a,a.length);
end = System.currentTimeMillis();
for(int i = 1; i < a.length; i++){
if(a[i-1] > a[i]){
System.out.println("Failed");
break;
}
}
System.out.println("milliseconds " + (end-bgn));
}
}