1 of 17

THE TWO-WAY MERGE

​

By

​

Dept. of CSE

PVPSIT, Kanuru.

​

​

PRASAD V. POTLURI SIDDHARTHA INSTITUTE OF TECHNOLOGY

2 of 17

  • Problem: Merge two arrays of integers, both with their elements in ascending order, into a single ordered array.
  • Algorithm development: Merging two or more sets of data is a task that frequently performed in computing.
  • Consider the two arrays:

​

Dept of CSE

2025 - 26

THE TWO-WAY MERGE

PVPSIT (Autonomous)

Problem Solving Techniques

3 of 17

  • The origins (array a or b) are written above each element in the c array.

​

​

​

  • Consider the smallest merging problem.

​

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

4 of 17

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

5 of 17

  • An overall structure we could use is:

​

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

6 of 17

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

7 of 17

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

8 of 17

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

9 of 17

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

10 of 17

  • A single procedure mergecopy can be used to implement these merging and copying steps.

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

11 of 17

  • For example if a ends first we can use:

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

12 of 17

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

13 of 17

Dept of CSE

2025 - 26

1

PVPSIT (Autonomous)

Problem Solving Techniques

14 of 17

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

15 of 17

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

16 of 17

  • Notes on design
  • For two input arrays of sizes m and n the number of comparisons vary from 2 to (n+m+1) to complete the task.
  • Applications:
  • Sorting, tape sorting, data processing.

Dept of CSE

2025 - 26

PVPSIT (Autonomous)

Problem Solving Techniques

17 of 17

  • 5.1.4 Design an algorithm for merging three arrays.

Dept of CSE

2025 - 26

Supplementary Problem

PVPSIT (Autonomous)

Problem Solving Techniques