scandum / blitsort Goto Github PK

Could you also add plots of a benchmark with different number of items in the array (as you did in benchmarks of Quadsort)?

Especially including 4-items, 8-items, 16-items, 32-items, 230_000-items, 300_000-items, and 400_000-items array runs (i.e. very low number of items and then very large number considering its limited 512 stack).

Hi, I wanted to ask about the complexity of the number of swaps/moves/assignments that come from the merging algorithm. The table only gives the complexity of the comparisons and extra memory used.

The description about the merging algorithm let it sound similiar to Symmerge and Recmerge:

A rotate merge sort uses rotations to partition two sorted arrays until they're small enough to be merged using auxiliary memory. Blitsort does so by taking the center element of the first array, using a binary search to find all elements smaller than the center element in the second array, and performing an array rotation. It does so recursively until a partition becomes small enough to be merged.

It probably recursively halves the size and rotates. I assume, the number of swaps/moves/assignments is O(m*Log2(m+n)) for two sorted sequences of sizes m and n, where m <= n. This would then result in a total complexity for blitsort of O(N*Log2(N)) comparisons and O(N*Log2(N)*Log2(N)) swaps/moves, if my assumption is correct. This would also be in line with the observation:

Performance on larger arrays degrades steadily

To sum up my question: Has blitsort a total worst-case complexity of O(N*Log2(N)) or O(N*Log2(N)*Log2(N))?

I wrote a simple test program. The output revealed qsort is better than blitsort on ARM macOS when sort the random int.
And on ARM macos, the size of long long and size of long double maybe is the same.
I used gcc to compile the code, compiler said duplicated value 8byte. So I commented the line and compiled successfully.
I don't know wether the qsort implementation in c is optimized on ARM Macos or not.I'm just a noob, the code maybe have some errors. You can point out my error. My operating system is bigsur 11.0 on mac.
My code as follow:

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <sys/time.h>
#include <time.h>
#include <errno.h>
#include <math.h>

#include "blitsort.h"

int cmp_int (const void * a, const void * b)
{
return ( (int)a - (int)b );
}

long long utime()
{
struct timeval now_time;
gettimeofday(&now_time, NULL);
return now_time.tv_sec * 1000000LL + now_time.tv_usec;
}

int main(){
int a[100000],b[100000],c[100000];
int seed = time(NULL);
srand(seed);
long long assignment_start_one = utime();
for(int i = 0;i < 100000;i++){
a[i] = rand();
}
for(int j = 0;j < 100000;j++){
b[j] = a[j];
c[j] = a[j];
}
long long assignment_end_one = utime();
printf("Assignment time: %lld. \n",assignment_end_one - assignment_start_one);
long long start = utime();
blitsort(b,100000,sizeof(int),cmp_int);
long long end = utime();
long long total = end - start;
long long start_qsort = utime();
qsort(c,100000,sizeof(int),cmp_int);
long long end_qsort = utime();
long long total_qsort = end_qsort - start_qsort;
printf("Blitsort time: %lld. \n",total);
printf("Qsort time: %lld. \n",total_qsort);
return 0;
}

Hello!

When building code I get lots of errors (1370 exactly). Most of them are "use of undeclared identifier" or "unknown type name". Any help here?.

Also, what is supposed I have to pass in the last parameter of blitsort func (type CMPFUNC*)?

Thanks in advance.