Problem InsertionSort

Hello guy’s, i have a problem whit this function, i not have a correct output the vector in correct order. I not found the problem, please help me.

The code of my funcition:

[codebox]void global insertion(int *v, int tam){

int i = blockDim.x * blockIdx.x + threadIdx.x; 

int a;

int j = blockDim.x * blockIdx.x + threadIdx.x;   

if(i<=tam){

a = v[i];

    while(v[j-1] > a){

v[j] = v[j-1];

j--;}

v[j] = a;   

}= ';[/codebox]

where tam = dimension; 512*1048

Tthx

Hello guy’s, i have a problem whit this function, i not have a correct output the vector in correct order. I not found the problem, please help me.

The code of my funcition:

[codebox]void global insertion(int *v, int tam){

int i = blockDim.x * blockIdx.x + threadIdx.x; 

int a;

int j = blockDim.x * blockIdx.x + threadIdx.x;   

if(i<=tam){

a = v[i];

    while(v[j-1] > a){

v[j] = v[j-1];

j--;}

v[j] = a;   

}= ';[/codebox]

where tam = dimension; 512*1048

Tthx

Hi Perry I expect that the problem is that with parallel programming many threads execute exactly the same line of code at once.

The insertion sort is dependant on all the elements of v from 0 to i-1 already being sorted i.e. it relies on being run by a single thread.
with parallel programming if several threads all have a value that should be inserted at v[99] then they will overwrite each others values.

As the classic insertion sort relies on being run by a single thread it can only be used when each thread works in its own array, for parallel programming there are other sorts that work.

Hi Perry I expect that the problem is that with parallel programming many threads execute exactly the same line of code at once.

The insertion sort is dependant on all the elements of v from 0 to i-1 already being sorted i.e. it relies on being run by a single thread.
with parallel programming if several threads all have a value that should be inserted at v[99] then they will overwrite each others values.

As the classic insertion sort relies on being run by a single thread it can only be used when each thread works in its own array, for parallel programming there are other sorts that work.