I needed an efficient sorting method to make my collision checks not be O(n^2) so I came up with a tree based sorting algorithm:

(original data set: 51,50,9000,1,60,100,82,80,0,52,51,50,1536,48,8,6558,2,5644,1,45)

Here's the code for it:

code:

void treesort()

{

int data[20] = {51,50,9000,1,60,100,82,80,0,52,51,50,1536,48,8,6558,2,5644,1,45};

int num_items = 20;

int check=0;

int tmp=0;

int node=0;//current node

int c_node=0;//comparison node

//treeify

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

//enforce rule that parents must be higher value

for (int i2=i+1;i2>1;i2/=2){

check++;

c_node =(i2/2)-1;

node = i2-1;

if (data[node]>data[c_node]){

tmp=data[c_node];data[c_node]=data[node];data[node]=tmp;//swap

}

else {break;}

}

}

//print

printf("tree before sort:\n");

for (int i=0; i<num_items; i++){

printf("%d ",data[i]);

}

printf("\nnumchecks: %d\n",check);

//sort

int last = num_items-1;

for (int i=num_items-1-((num_items-1)&1); i>1; i-=2){

check++;

//if right hand branch then enforce rule that it must be smaller than left hand branch

if (data[i]>data[i-1]){

tmp=data[i-1];data[i-1]=data[i];data[i]=tmp;

}

//then check if next pair is bigger

for (int i2=last;i2>i;i2--){

check++;

//check against current branch lower val, if higher then low val check against current branch higher val

if (data[i]<data[i2]){

check++;

tmp=data[i2];data[i2]=data[i];data[i]=tmp;//swap

if (data[i-1]<data[i]){

tmp=data[i];data[i]=data[i-1];data[i-1]=tmp;//swap

last = i-1;

}

else{last = i;}

}

}

}

//print

printf("sorted values:\n");

for (int i=0; i<num_items; i++){

printf("%d ",data[i]);

}

printf("\nnumchecks: %d\n",check);

}

Didn't research into any specifics regarding current sorting methods, this pretty much came from some mad scribblings and going through it by hand on paper. I did look into how a basic tree structure is made to figure out how I could build a tree without using a data structure with left/right branches, but then I just realized each pair of numbers represents a branch and n/2 moves up and n*2 moves down and it was pretty simple from there. I don't think the order of objects is swapped if they're the same value when they're tree-ified, I may be wrong but it's not really important to me... The complexity in total is O(3(nlogn))? I don't really understand the n*log(n) business or how that comes about but it's definitely not n^2 or linear.

If you can spot any errors or possible optimizations it'd be great if you'd let me know.