Scribd
Upload
3 views3 pages

Merge Sort Process

The document provides a detailed explanation of the Merge Sort algorithm, including pseudo code and a step-by-step merging process for sorting an example array. It illustrates how individual elements are merged into larger sorted arrays, culminating in a final sorted output. The final sorted array from the example is [1, 2, 3, 4, 5, 6, 7, 8].

Uploaded by

irfn94795
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
3 views3 pages

Merge Sort Process

The document provides a detailed explanation of the Merge Sort algorithm, including pseudo code and a step-by-step merging process for sorting an example array. It illustrates how individual elements are merged into larger sorted arrays, culminating in a final sorted output. The final sorted array from the example is [1, 2, 3, 4, 5, 6, 7, 8].

Uploaded by

irfn94795
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

MERGE SORT – CODE + COMPARISON TABLE

Example Array:

[8, 3, 5, 4, 7, 6, 1, 2]

----------------------------------------------------

PROGRAM (Pseudo Code)

----------------------------------------------------

mergeSort(arr, left, right):

if left < right:

mid = (left + right) / 2

mergeSort(arr, left, mid)

mergeSort(arr, mid+1, right)

merge(arr, left, mid, right)

merge(arr, left, mid, right):

create L[] and R[]

i = 0, j = 0, k = left

while i < size(L) and j < size(R):

if L[i] < R[j]:

arr[k] = L[i]

i++

else:

arr[k] = R[j]

j++

k++

copy remaining elements

----------------------------------------------------

LEVEL 1: MERGE SINGLE ELEMENTS

----------------------------------------------------

Merge: [8] & [3]

8 > 3 → else → 3 placed


8 placed

Merge: [5] & [4]

5 > 4 → else → 4 placed

5 placed

Merge: [7] & [6]

7 > 6 → else → 6 placed

7 placed

Merge: [1] & [2]

1 < 2 → if → 1 placed

2 placed

----------------------------------------------------

LEVEL 2: MERGE TWO■ELEMENT ARRAYS

----------------------------------------------------

Merge: [3, 8] & [4, 5]

3 < 4 → if → 3 placed

8 > 4 → else → 4 placed

8 > 5 → else → 5 placed

8 placed

Merge: [6, 7] & [1, 2]

6 > 1 → else → 1 placed

6 > 2 → else → 2 placed

6 placed

7 placed

----------------------------------------------------

FINAL MERGE

----------------------------------------------------

Merge: [3,4,5,8] & [1,2,6,7]

3 > 1 → else

3 > 2 → else
3 < 6 → if

4 < 6 → if

5 < 6 → if

8 > 6 → else

8 > 7 → else

8 placed

FINAL SORTED OUTPUT:

[1, 2, 3, 4, 5, 6, 7, 8]

You might also like