How do you make POSIX threads interact with a sorting algorithm?

[neodregan]

I want to try to understand the method of using POSIX threads to interact with a sorting algorithm such as the odd-even transposition sort.

I have written my program to do a odd-even transposition sort without threads and this is my current result:

./sort data
File opened successfully.
The numbers are:
20
19
18
17
16
15
Before sort::
20 19 18 17 16 15

After phase 0:
19 20 17 18 15 16

After phase 1:
19 17 20 15 18 16

After phase 2:
17 19 15 20 16 18

After phase 3:
17 15 19 16 20 18

After phase 4:
15 17 16 19 18 20

After phase 5:
15 16 17 18 19 20

After sort::
15 16 17 18 19 20

This is the current part of my code where I am trying to make the threads correctly and do the start function from pthread_create():

int list[20];
int n = 20;
int param[10];
pthread_t threads[10];

void *startPoint( void *arg )
 {
   //threads interact with odd-even sorting here
}

int main(int argc, char** argv)
{
        pthread_attr_t tattr; // thread attributes
        pthread_t tid;
	readLINE(argv[1]); //reads the data file and loads it into the list array

        pthread_attr_init (&tattr);
        pthread_attr_setscope (&tattr, PTHREAD_SCOPE_SYSTEM);
		
		display(list, n, "Before sort:");
		
		
		//MULTI-THREADED SECTION for SORTING
		for(int count = 0; count < n/2; count++)
		{
			param[count] = count*2;
		        pthread_create( &threads[ count], NULL, startPoint, (void*) &param[count]);	
		}
		
		//END OF MULTI-THREADED SECTION
		
                //Regular sort w/o multi-threading
		//Odd_even_sort(list, n);
		
		display(list, n, "After sort:");

        exit(0);
}

I am not really sure how many threads I need to create for each phase of sorting. I can see it visually with a picture, but to implement it is confusing.

Here's a picture:

[IMG]http://img708.imageshack.us/img708/9743/imagecl.jpg[/IMG]

Also, how do I make the threads interact with the actual sorting procedure after I've created them?

[Banfa]

I think you will find it very hard to code this sorting algorithm as anything other than single threaded. The problem is that every phase of your algorithm depends on the previous phase so no phase can be done independently of any other.

If you want to use multiple threads for sorting you will need to choose an algorithm that is suited to rather than the simple sort you appear to be using. For example a merge sort that sorts a list by recursively into 2 lists sorting each of those lists and then merging the 2 sorted lists back into 1.

Sorting the 2 halfs of a list could easily be done by 2 threads.

Merge sort is by no means the only algorithm that leads itself to multiple threads in this manor.