Parallel merge sort

[yashrsb]

Description of the problem

I propose parallel merge sort in python. Parallel Merge Sort first divides the unsorted list into smallest possible sub-lists, compares it with the adjacent list, and merges it in a sorted order. It implements parallelism very nicely by following the divide and conquer algorithm.

References/Other comments

https://stanford.edu/~rezab/classes/cme323/S16/notes/Lecture04/cme323_lec4.pdf

[yashrsb]

please assign me this issue.

[divs30]

@TechnoPhasePRO go ahead with this, if you are not working on any other issue right now.
Please read the complete plan of action at https://github.com/codezonediitj/pydatastructs/wiki/Plan-of-Action-for-the-Projects

[czgdp1807]

@divs30 Thanks for the guidance.
@TechnoPhasePRO For starting please come up with an API design and comment the same in this issue.
Whenever you will make a PR, it will be linked with this issue and will show up in the Assignee column here.

[nehasangeetajha]

Please assign it to me also? I want to try this one

[czgdp1807]

In addition to this comment. If @TechnoPhasePRO doesn't come up with an API design for some time, you can give your own and make a PR afterwards. Meanwhile, you can see other issues in this list.

[manaswinidas]

@TechnoPhasePRO are you still working on this? Just to check whether you are on it.

[yashrsb]

@TechnoPhasePRO are you still working on this? Just to check whether you are on it.

ma'm i am still working on this project . I had a busy week and couldn't find time to complete it. I will be submitting it soon.

[Meenakshi2000]

please assign me this

[czgdp1807]

@Meenakshi2000 We don't assign issues. See our issue policy.

[yashrsb]

@czgdp1807 sir, this please review my api .

following API is designed based on parallel merge sort regarding the mentioned issue.

Libraries used :
import math
import multiprocessing
import random
import sys
import time

def merge(*args):
Support explicit left/right args, as well as a two-item
tuple which works more cleanly with multiprocessing.
sorted elements are merged merged together.
This will return the sorted merged array.

def merge_sort(data):
data : It takes data as parameter that consists of original array.
length : To check size of array
middle : To find the middle index of array
left : This will make First half of the array from the the middle position.
right : This will make Second half of the array from the middle position.

def merge_sort_parallel(data):
processes : It takes data as parameter that is array of elements.
pool : Creates a pool of worker processes, one per CPU core.
size : creates a (n/p) size process to be assigned to CPU core.
data : Each partition is now sorted - we now just merge pairs of these together using the
worker pool, until the partitions are reduced down to a single sorted result.
while len(data) > 1 :
extra : If the number of partitions remaining is odd, we pop off the
last one and append it back after one iteration of this loop,
since we're only interested in pairs of partitions to merge.
This will return array sorted in parallel merge sort.

if __name__ == "__main__":
size : a random array of dynamic size is selected
data_unsorted : this will create a global original array to sort data by merge_sort,
merge_sort_parallel. Random array size is selected and array is generated.
This will return time taken by merge sort an parallel merge sort to sort the array.

[czgdp1807]

IMHO, we can use threads instead of processes.
P.S. - Due to GIL, using threads won't be of much use but porting the implementation to other languages like C++ would be really easy.
Processes have an overhead. Please modify the API by editing your comment. In addition, we need a iterative bottom up approach for merge sort rather than recursive top down as recursion too has it's own overhead.