Scribd
Upload
2 views18 pages

Sorting Algorithms: Insertion & Merge Sort

The document provides an introduction to sorting algorithms, focusing on Insertion Sort and Merge Sort, including their concepts, algorithms, and analysis of their running times. It discusses the importance of analyzing algorithms in terms of resource requirements like memory and CPU cycles. The notes also reference material from a textbook and a Coursera course on algorithm design and analysis.

Uploaded by

Muhammad Imaz
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
2 views18 pages

Sorting Algorithms: Insertion & Merge Sort

The document provides an introduction to sorting algorithms, focusing on Insertion Sort and Merge Sort, including their concepts, algorithms, and analysis of their running times. It discusses the importance of analyzing algorithms in terms of resource requirements like memory and CPU cycles. The notes also reference material from a textbook and a Coursera course on algorithm design and analysis.

Uploaded by

Muhammad Imaz
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

Introduction to Sorting

CS-310: Analysis of Algorithm


Waheed Iqbal

Punjab University College of Information Technology (PUCIT)


University of the Punjab, Lahore, Pakistan.
Credit

These notes contain material from Chapter 2, Design and


Analysis of Algorithms by Cormen, Leiserson, Rivest,
and Stein (3rd Edition).
Socks Pairing Problem
Socks Pairing Problem (Cont.)
• Thing about applying Hashing to solve socks pairing
problem…..
Sorting Problem
Insertion Sort (Concept)
Insertion Sort (Algorithm)
Analysing Algorithm
• Analysing algorithm means predicting resources the
algorithm requires, for example:
• memory, communication bandwidth, CPU cycles etc

• RAM (random-access machine) model: generic one


process model which assumes instructions execute one
after another
• The RAM model contains instructions commonly found in real
computers: arithmetic, data movement (load, store, copy), and
control (conditional and unconditional branch, subroutine call and
return).
• Each such instruction takes a constant amount of time.
Insertion Sort (Analysis)
Insertion Sort (Analysis)

Running Time?
Insertion Sort (Analysis Cont.)
• What are the best and worst-case running times of
INSERTION-SORT?

• Lets try to solve T(n)for best case and worst case.


Insertion Sort (Analysis Cont.)
Insertion Sort Best Case Running Time

Insertion Sort Worst Case Running Time


Merge Sort (Introduction)
Divide-and-conquer based algorithm with O(nlogn) running
time complexity.

Divide: divide the input into number of subparts

Conquer: solve sub-problems recursively

Combine: combine the solution of sub problems into the


solution for the original problem
Merge Sort (Concept)
Merge Sort (Algorithm)
Merge Sort (Merge Call)
Merge Sort (Merge Call Simplified)

Source: Coursera course “Design and Analysis” course available at coursera by Tim Roughgarden, Stanford University.
Merge Sort Running Time Complexity
• Lets discuss how Merge Sort running time complexity is
O(nlogn)!

1. How many levels of this recursion tree have as a


function of n (size of input array)?
2. Running time complexity of merge call?

You might also like