How can the odd-even transposition sort algorithm be parallelized in an eficient way using PThreads?-CodePudding

I've recently started to study about parallel computing. I am currently reading about parallel sorting and searching algorithms. From the well known bubblesort algorithm, I found out about the Odd_Even_Transposition_Sort algorithm. For those who don`t already know, the last one can be parallelized more easily. I give two snippets of code for both algorithms below:

function bubbleSort(list) {
  sorted = false;
  while (!sorted) {
    sorted = true;
    for (var i = 0; i < list.length - 1; i  ) {
      if (list[i] > list[i   1]) {
        swap(list[i], list[i   1]);
        sorted = false;
      }
    }
  }
}

function oddEvenSort(list) {
  for (var k = 0; k < list.length; k  ) {
    for (i = 0; i < list.length - 1; i  = 2) {
      if (list[i] > list[i   1]) {
        swap(list[i], list[i   1]);
      }
    }
    for (i = 1; i < list.length - 1; i  = 2) {
      if (list[i] > list[i   1]) {
        swap(list[i], list[i   1]);
      }
    }
  }
}

Now to reach to my initial question, I don't understand how can the odd-even algorithm be parallelized efficiently. What I mean by efficiency? Using only as much threads as the number of cores your laptop has, or in any case, in a close range. From what I understand the implementation given here https://www.geeksforgeeks.org/odd-even-transposition-sort-brick-sort-using-pthreads/, wouldn't apply nicely to big arrays. In this example, there are only 8 elements and the number of threads (n 1) / 2 = 4 is small. But for large arrays, for instance 500 elements wide which isn't even so big, the number of threads created I believe will create overhead. The problem, I think, comes from the fact that every comparison and potential swap in either the odd or even phase is put on a specific thread. Thus the more elements you have the more threads will be created. So how can the problem be parallelized for an array of let`s say 1000 elements using only 4 threads?

P.S.: Furthermore, I'm using Pthreads so any answer or piece of code written this way will help. Besides the answer, any refferrence to places(books, sites etc) where I can learn parallel computing better will be well-received.

CodePudding user response：

To do it with only p threads, the idea is to give blocks of size n/p for each thread, sort each block with a fast algorithm (like quick sort) and communicate last element of thread i with thread i 1 and first element of thread i 1 with thread i for the odd-even transposition (to combine the sort of each block).

I suggest you give a look at the explanation here for deeper details and an implementation.