UNIVERSITY OF ENGINEERING AND TECHNOLOGY, TAXILA

DEPARTMENT OF COMPUTER SCIENCE

http://web.uettaxila.edu.pk

Lab Manual 04
CS201: Data Structure and Algorithms
Class: BSCS-2k21
Lab 4: Sorting techniques-II

Instructors:
Mr. Awais Mehmood
awais.mehmood@uettaxila.edu.pk

&
Mr. M. Faheem Saleem
muhammad.faheem@uettaxila.edu.pk

CS201: Data Structures and Algorithms Page 1

 UNIVERSITY OF ENGINEERING AND TECHNOLOGY, TAXILA
DEPARTMENT OF COMPUTER SCIENCE
http://web.uettaxila.edu.pk

Lab Manual 4
Introduction
This lab is in continuation to the previous lab which is about sorting Operations on Arrays in
C++.
Objectives
The objectives of this session is to understand the various sorting operations on arrays in C++.
Tools/Software Requirement
Dev C++
Goals for today’s lab:

• Understanding sorting array operations and write it’s algorithm.

• Convert algorithm to practical implementation.

Sorting Arrays:-

The process of arranging data in a specified order is called sorting. Numeric type data may be
arranged either in ascending or in descending order. Similarly character type data may be
arranged in alphabetical order.

There are different methods to sort data into a list. The most commonly used methods are:

1. Merge Sort
2. Quick Sort

1) Merge Sort

Think of it as a recursive algorithm that continuously splits the array in half until
it cannot be further divided. This means that if the array becomes empty or has
only one element left, the dividing will stop, i.e., it is the base case to stop the
recursion. If the array has multiple elements, split the array into halves and
recursively invoke the merge sort on each of the halves. Finally, when both
halves are sorted, the merge operation is applied. Merge operation is the
process of taking two smaller sorted arrays and combining them to eventually
make a larger one.
Illustration:
To know the functioning of merge sort, let’s consider an array arr[] = {38, 27, 43,
3, 9, 82, 10}

CS201: Data Structures and Algorithms Page 2

 UNIVERSITY OF ENGINEERING AND TECHNOLOGY, TAXILA
DEPARTMENT OF COMPUTER SCIENCE
http://web.uettaxila.edu.pk

• At first, check if the left index of array is less than the right index, if yes then
calculate its mid point

• Now, as we already know that merge sort first divides the whole array
iteratively into equal halves, unless the atomic values are achieved.
• Here, we see that an array of 7 items is divided into two arrays of size 4 and
3 respectively.

• Now, again find that is left index is less than the right index for both arrays, if
found yes, then again calculate mid points for both the arrays.

• Now, further divide these two arrays into further halves, until the atomic units
of the array are reached and further division is not possible.

CS201: Data Structures and Algorithms Page 3

 UNIVERSITY OF ENGINEERING AND TECHNOLOGY, TAXILA
DEPARTMENT OF COMPUTER SCIENCE
http://web.uettaxila.edu.pk

• After dividing the array into smallest units, start merging the elements again
based on comparison of size of elements.
• Firstly, compare the element for each list and then combine them into
another list in a sorted manner.

• After the final merging, the list looks like this:

CS201: Data Structures and Algorithms Page 4

 UNIVERSITY OF ENGINEERING AND TECHNOLOGY, TAXILA
DEPARTMENT OF COMPUTER SCIENCE
http://web.uettaxila.edu.pk

Algo:

Algo:
step 1: start
step 2: declare array and left, right, mid variable
step 3: perform merge function.
if left > right
return
mid= (left+right)/2
mergesort(array, left, mid)
mergesort(array, mid+1, right)
merge(array, left, mid, right)
step 4: Stop
Follow the steps below the solve the problem:
MergeSort(arr[], l, r)
If r > l
• Find the middle point to divide the array into two halves:
• middle m = l + (r – l)/2
• Call mergeSort for first half:
• Call mergeSort(arr, l, m)
• Call mergeSort for second half:
• Call mergeSort(arr, m + 1, r)
• Merge the two halves sorted in steps 2 and 3:
• Call merge(arr, l, m, r)

merge(array, left, middle, right)

Begin
nLeft := m - left+1
nRight := right – m
define arrays leftArr and rightArr of size nLeft and nRight respectively
for i := 0 to nLeft do
leftArr[i] := array[left +1]
done
for j := 0 to nRight do
rightArr[j] := array[middle + j +1]
done
i := 0, j := 0, k := left

CS201: Data Structures and Algorithms Page 5

 UNIVERSITY OF ENGINEERING AND TECHNOLOGY, TAXILA
DEPARTMENT OF COMPUTER SCIENCE
http://web.uettaxila.edu.pk

while i < nLeft AND j < nRight do

if leftArr[i] <= rightArr[j] then
array[k] = leftArr[i]
i := i+1
else
array[k] = rightArr[j]
j := j+1
k := k+1
done
while i < nLeft do
array[k] := leftArr[i]
i := i+1
k := k+1
done
while j < nRight do
array[k] := rightArr[j]
j := j+1
k := k+1
done
End

CS201: Data Structures and Algorithms Page 6

 UNIVERSITY OF ENGINEERING AND TECHNOLOGY, TAXILA
DEPARTMENT OF COMPUTER SCIENCE
http://web.uettaxila.edu.pk

Class task:
Implement merge sort
Home task:
Write algo of quick sort and implement it

CS201: Data Structures and Algorithms Page 7