Hello, i need some input on the parallelisation of quicksort. If anyone knows a more appropriate forum/list than this, please tell me =)
I've written 2 different approaches to the quicksort parallelisation. 1. The "master" server splits the array of numbers into N seperate parts, where N is the number of available clients or slave servers. Each slave then does a quicksort on its own subarray - finally all slaves sent their subarray to the master. The master then does a quicksort on the presorted list. *This was done for the assumption that presorted list sort faster with quicksort than very unordered/random numbers lists. 2. The "master" server finds out the MIN and MAX value from the to sorting array (iterates through all numbers). Then it will assign boundaries to each slave starting from MIN for the first slave, to MAX for the last slave (i.e. for 2 slaves it would be from MIN -> MAX/2 and MAX/2+1 -> MAX). The master then sends the whole array to each slave, each slave filters through the whole array all numbers within their own boundary (slave 1 for example would find all numbers between MIN -> MAX/2), after that it would quicksort the resulting array. Finally each slave server would sent the resulting subarrays to the master in the correct sequence - meaning that the master server would not be needed to do any sorting at all - only append the results i.e. slave1 starts first, then slave2... This has the advantage that only minimum network "messages" are sent (not traffic). Anyone has any different ideas ? I've read a few papers about it - the basic approach would be to parallel the divide and conquer part - which would result in ALOT of network messages... Thank you __________________________________________________ Do You Yahoo!? Tired of spam? Yahoo! Mail has the best spam protection around http://mail.yahoo.com
