an implementation of insertion sort, insert without move element

[Gestorm]

Suppose we have an array a[N], the idea is: build another array, int
next[N], for each 0<i<N, next = next position of a in the sorted
array, if a is the max, then next is undefined. For example, let
the unsorted array is
a[] = {5, 4, 2, 1, 3};
then
next[]
would be
{undefined, 0, 4, 2, 1}
after sorted.
The process of sort is the process of building array next[]. Finally,
build sorted a[] according to
next[]. But at the last step, I cannot build a[] according to next[]
directly, so I have to build another array tmp[N] to store the sorted
sorted result, then copy it back to array a[], but I believe there is
some way to do it. Does anyone who does well in algo analysis can
help me to analyze my algo$B!)(BI want to know if my algo is more efficient
than the original one. And is there any way to build a[] directly at
the last step? Thanks!
The following is my code, we assume that the element type is int.
#include<stdio.h>
void myInsertionSort(int a[], int size)
{
int *next, *tmp;
next = malloc(size * sizeof(int));
tmp = malloc(size * sizeof(int));
int first = 0, last = 0, max;
int i;
for(i = 1, max = a[0]; i < size; i++){
if(a < max){
if(a <= a[first]){
next = first;
first = i;
}else{
int j = first;
while(a > a[next[j]])
j = next[j];
next = next[j];
next[j] = i;
}
}else{
next[last] = i;
max = a;
last = i;
}
}
int j;
for(i = 0, j = first; i < size; i++){
tmp = a[j];
j = next[j];
}
for(i = 0; i < size; i++)
a = tmp;
free(next);
free(tmp);
}
int main()
{
int a[] = {3, 9, 6, 4, 1, 5, 7, 2, 10, 8, 87, 95, 456, 127, 54,
784, 65, 313, 75};
#define ARRAY_LENTH(array) (sizeof ((array)) / sizeof(int))
myInsertionSort(a, ARRAY_LENTH(a));
int i;
for(i = 0; i < ARRAY_LENTH(a); i++)
printf("%d, ", a);
return 0;
}