Question

Q2. Apply Merge Sort to sort the list E, X, A, M, P, L, E in alphabetical order.

Answer 1

1.divide
(E X AM P L E)
(E X A M)(P L E)
(E X ) (A M) (P L ) (E)
2.conquer
(X E) (A M) (L P)(E)
(A E M X) (E L P)
(A E E M L P X)

Answer 2

Hey,i just want to add a small comment. Go with Faisal's solution.It is straight and 100% correct.Best regards,crypto

Answer 3

Best solution is here.

Answer 4

//mergesort algorithm

MergeSort(A[0..n-1])

ifn > 1

copy A[0..floor(n/2) - 1] to B[0..floor(n/2) - 1]

copy A[floor(n/2) .. n-1] to C[0..ceil(n/2) - 1]

MergeSort(B[0..floor(n/2) - 1])

MergeSort(C[0..ceil(n/2) - 1])

Merge(B,C,A)

Merge(B[0..p-1], C[0..q-1], ), A[0..p+q-1])

i<- 0; j <- 0; k <- 0

while i < p and j < q do

if B[i] <= C[j]

A[k] <- B[i]; i <- i + 1

else A[k] <- C[j]; j <- j + 1

k <- k + 1

ifi = p

copy C[j..q - 1] to A[k..p + q -1]

else copy B[i..p - 1] to A[k..p + q -1]

Note that Merge is not called until there are two subarrays of size1. The

first call to Merge is marked by an asterisk:

0 1 2 3 4 5 6

E X A M P L E

/

EX A M P L E

//

E XAMPLE

| / / /

|X A M PLE

| / / /

*AXMPEL

/ /

AEXELMP

/

AEELMPX

Merge iscalled in 6 times. The sorted subarray for each call islistedhere:

1 A X

2 A E X

3 M P

4E L

5 E L MP

6 A E E L M P X