0

4.4kviews

Write an algorithm for merge sort and comment on its complexity.

**1 Answer**

0

4.4kviews

Write an algorithm for merge sort and comment on its complexity.

0

290views

written 7.4 years ago by | • modified 5.6 years ago |

```
// algorithm for merge sort
```

**MERGE (ARR, BEG, MID, END)**

```
Step 1: [INITIALIZE] SET I = BEG, J = MID + 1, INDEX =
Step 2: Repeat while (I <= MID) AND (J<=END)
IF ARR[I] < ARR[J]
SET TEMP[INDEX] = ARR[I]
SET I = I + 1
ELSE
SET TEMP[INDEX] = ARR[J]
SET J = J + 1
[END OF IF]
SET INDEX = INDEX + 1
[END OF LOOP]
Step 3: [Copy the remaining elements of right sub-array, if any]
IF I > MID
Repeat while J <= END
SET TEMP[INDEX] = ARR[J]
SET INDEX = INDEX + 1, SET J = J + 1
[END OF LOOP]
[Copy the remaining elements of left sub-array, if any]
ELSE
Repeat while I <= MID
SET TEMP[INDEX] = ARR[I]
SET INDEX = INDEX + 1, SET I = I + 1
[END OF LOOP]
[END OF IF]
Step 4: [Copy the contents of TEMP back to ARR] SET K=
Step 5: Repeat while K < INDEX
SET ARR[K] = TEMP[K]
SET K = K + 1
[END OF LOOP]
Step 6: END
```

**MERGE_SORT(ARR, BEG, END)**

```
Step 1: IF BEG < END
SET MID = (BEG + END)/2
CALL MERGE_SORT (ARR, BEG, MID)
CALL MERGE_SORT (ARR, MID + 1, END)
MERGE (ARR, BEG, MID, END)
[END OF IF]
Step 2: END
```

**Complexity of merge sort :**
The running time of merge sort in the average case and the worst case can be given as O(n log n). Best time complexity is also same as worst and average time complexity.

ADD COMMENT
EDIT

Please log in to add an answer.