Assignments

Parallel Merge Sort – implement a classic sorting algorithm utilising concurrency

The aim of our project was to implement a classic sorting algorithm utilising concurrency. We decided on Merge Sort because of its inherent parallelism. Sorting in general has been hailed as a cornerstone in Computer Science [SHG09], as many computer algorithms rely heavily upon it. Such an algorithm is for example the classic Kruskal algorithm for constructing a minimum spanning tree of an undirected graph [Kru56]. Merge Sort is based on the popular Divide-and-conquer approach[CLR02], where the problem at hand is broken into smaller problems of similar nature, which are inturn solved recursively, and the solutions are then combined.The logic of Merge Sort itself is very straightforward. It consists in dividing the array into two parts of approximately the same length (the difference between the lengths of the two subarrays is at most 

Follow me

Related Post