Chapter 6, Problem 6.5.2E

Program Plan Intro

Parallelism:

The state of being parallel and having correspondence among them is referred as parallelism. Two or more tasks can be performed simultaneously, without affecting the performance of the either one.

Given Information:

It is given that for the following recursive merge sort algorithm, the basic idea is to divide an unsorted list x of m elements into two sub lists of about half the size of the original list.

The merge step is carried out by the following code:

//Merge soft algorithm where m is the array passed as parameter

Mergesort(m)

//define variable left, right and result

var list left, right, result

//check if length of the array is less than "1"

if length(m) ≤ 1

//if length of array is less than "1" then return

return m

else

// set length of array as middle variable

var middle = length(m)/2

for each x in m after middle

//add the integer value to the left

add x to left

for each x in m after middle

//add the itneger value to the right

add x to right

//Sort the left array

left = Mergesort(left)

//Sort the right array

right = Mergesort(right)

//merge the sorted left and right array

result = Merge(left, right)

return result

The merge step is mentioned below:

//merge the left and right sorted array

Merge(left, right)

//declare variable result

var list result

//While loop continues till elements exist in array

while length(left) >0 and length(right) > 0

/* check if first value of left array is less than first value of right array */

if first(left) ≤ first(right)

//add first of left array to the result //array

append first(left) to result

left = rest(left)

else

//add first of right array to the result //array

append first(right) to result

right = rest(right)

//check if length of left array is greater than 0

if length(left) >0

//add rest of left array to the result array

append rest(left) to result

if length(right) >0

//add rest of right array to the result array

append rest(right) to result

//return result array

return result