[go: up one dir, main page]
Scribd
Upload
141 views8 pages

DSA Lab 5 Merge Sort

The document discusses merge sort, an algorithm with O(n log n) time complexity that works by dividing an array into halves and then merging the halves back together in a sorted order. It explains that merge sort first divides the array recursively until reaching single elements, then combines the single elements back into sorted arrays. The lab tasks involve implementing merge sort to merge two integer arrays and sort an array of characters recursively.

Uploaded by

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

DSA Lab 5 Merge Sort

The document discusses merge sort, an algorithm with O(n log n) time complexity that works by dividing an array into halves and then merging the halves back together in a sorted order. It explains that merge sort first divides the array recursively until reaching single elements, then combines the single elements back into sorted arrays. The lab tasks involve implementing merge sort to merge two integer arrays and sort an array of characters recursively.

Uploaded by

ABC
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPTX, PDF, TXT or read online on Scribd
You are on page 1/ 8

CSC-221 Data Structures and Algorithm

Bahria University Karachi Campus

Merge Sort Lab No. 5

ENGR. SANIYA SARIM


MERGE SORT

• Merge sort is a sorting technique based on divide and conquer


technique. With worst-case time complexity being Ο(n log n), it is
one of the most respected algorithms.

• Merge sort first divides the array into equal halves and then
combines them in a sorted manner.

CSC-221 Data Structures and Algorithm Bahria University Karachi Campus


How Merge Sort Works?

CSC-221 Data Structures and Algorithm Bahria University Karachi Campus


CSC-221 Data Structures and Algorithm Bahria University Karachi Campus
MERGE SORT ALGORITHM

• Merge sort keeps on dividing the list into equal halves until it can
no more be divided. By definition, if it is only one element in the
list, it is sorted. Then, merge sort combines the smaller sorted
lists keeping the new list sorted too.
• Step 1 − if it is only one element in the list it is already sorted,
return.
• Step 2 − divide the list recursively into two halves until it can no
more be divided.
• Step 3 − merge the smaller lists into new list in sorted order.
CSC-221 Data Structures and Algorithm Bahria University Karachi Campus
MERGE FUNCTION ALGORITHM

CSC-221 Data Structures and Algorithm Bahria University Karachi Campus


MERGE SORT ALGORITHM

CSC-221 Data Structures and Algorithm Bahria University Karachi Campus


Lab Tasks

1. Implement merge sort algorithm to merge two integer arrays into a third
array in sorted order.

2. Implement recursive method of merge sort algorithm to sort an array of


10 characters.

You might also like