Parallel Brick Sort

[nehasangeetajha]

Description of the problem

I would like to propose an odd-even transposition sort or brick sort. Odd-Even Transposition Sort is based on the Bubble Sort technique. It compares two adjacent numbers and switches them if the first number is greater than the second number to get an ascending order list. The opposite case applies to a descending order series.

Please assign me this issue.

[czgdp1807]

In computing, an odd–even sort or odd–even transposition sort is a relatively simple sorting algorithm, developed originally for use on parallel processors with local interconnections. It is a comparison sort related to bubble sort, with which it shares many characteristics.

This page says that it was originally developed for parallel threads/processors. So, IMO, we should add its parallel implementation with odd indices being sorted on one thread and even indices on another thread. Though before, that a nice API design should be proposed which can be applicable to other parallel sorting algorithms like parallel merge sort. We can develop a uniform API for all parallel sorting algorithms.

[czgdp1807]

Please assign me this issue.

See our issue policy at https://github.com/codezonediitj/pydatastructs/wiki/Issue-Policy

[Meenakshi2000]

How to contribute

[czgdp1807]

See, https://github.com/codezonediitj/pydatastructs/wiki/Plan-of-Action-for-the-Projects
For this issue specifically we need a parallel version of brick sort. You can think of an idea to make brick sort parallel and we can discuss over it further.

[MukundVaradarajan]

Hi, I would like to work on this. Is anyone else already working on it? I have got an idea to go about it.

@czgdp1807 can I start working on this? Any updates on this?

[czgdp1807]

@MukundVaradarajan Please start by proposing some API designs for brick sort. We need only it's parallel version implemented. IMO, the API for this can along the lines of parallel merge sort already there in the master.
See,

pydatastructs/pydatastructs/linear_data_structures/algorithms.py

Line 43 in 150c6c2

def merge_sort_parallel(array, num_threads, **kwargs):

[czgdp1807]

Parallel implementation of this algorithm is yet to be added.

[HarsheetKakar]

we can try one thread for odd and one thread for even part of the array.

[czgdp1807]

Some idea is given in #129 (comment)

[HarsheetKakar]

Some idea is given in #129 (comment)

I can start with a draft PR if its ok?

[czgdp1807]

Sure