Design and Analysis of Algorithms

EVEN 2026

Module 1: Sorting Algorithms

Jaypee Institute of Information Technology (JIIT)

A-10, Sector 62, Noida
 Sorting Techniques

Source: Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.).
MIT Press and McGraw-Hill. ISBN 0-262-03384-4. 1320 pp
2
Sorting – The Task
• Given an array
x[0], x[1], … , x[size-1]
reorder entries so that
x[0] <= x[1] <= . . . <= x[size-1]

Here, List is in non-decreasing order.

• We can also sort a list of elements in non-increasing order.

3
Sorting – Example
• Original list:
– 10, 30, 20, 80, 70, 10, 60, 40, 70

• Sorted in non-decreasing order:

– 10, 10, 20, 30, 40, 60, 70, 70, 80

• Sorted in non-increasing order:

– 80, 70, 70, 60, 40, 30, 20, 10, 10

4
Sorting Problem
• What do we want :
- Data to be sorted in order

0 size-1
x: Unsorted list

Sorted list

5
Issues in Sorting
Many issues are there in sorting techniques
• How to rearrange a given set of data?
• Which data structures are more suitable to store data prior
to their sorting?
• How fast the sorting can be achieved?
• How sorting can be done in a memory constraint situation?
• How to sort various types of data?

6
Sorting Algorithms

7
Sorting by Comparison
• Basic operation involved in this type of sorting
technique is comparison. A data item is compared
with other items in the list of items in order to find
its place in the sorted list.
• Insertion
• Selection
• Exchange
• Enumeration

8
Sorting by Comparison
Sorting by comparison – Insertion:
• From a given list of items, one item is considered at a time. The item
chosen is then inserted into an appropriate position relative to the
previously sorted items. The item can be inserted into the same list or to a
different list.
e.g.: Insertion sort
Sorting by comparison – Selection:
• First the smallest (or largest) item is located and it is separated from the
rest; then the next smallest (or next largest) is selected and so on until all
item are separated.
e.g.: Selection sort, Heap sort
Sorting by Comparison
Sorting by comparison – Exchange:
• If two items are found to be out of order, they are
interchanged. The process is repeated until no more exchange
is required.
e.g.: Bubble sort, Shell Sort, Quick Sort
Sorting by comparison – Enumeration:
• Two or more input lists are merged into an output list and
while merging the items, an input list is chosen following the
required sorting order.
e.g.: Merge sort

10
Sorting by Distribution
• No key comparison takes place
• All items under sorting are distributed over an auxiliary storage
space based on the constituent element in each and then grouped
them together to get the sorted list.
• Distributions of items based on the following choices
✔ Radix - An item is placed in a space decided by the
bases (or radix) of its components with which it is
composed of.
✔ Counting - Items are sorted based on their relative counts.
✔ Hashing - Items are hashed, that is, dispersed into a list
based on a hash function.
Note: This lecture concentrates only on sorting by comparison.

11
Insertion Sort

12
Lecture
CS 10001#07:
: Programming
© DSamantaand
Data Structures
Insertion Sort
General situation :
0 i size-1
x: smallest elements, sorted remainder, unsorted

i Compare and
Shift till x[i] is
larger.
i

0 j
size-1

13
Lecture
CS 10001#07:
: Programming
© DSamantaand
Data Structures
Insertion Sort
void insertionSort (int list[], int size)
{
int i,j,item;

for (i=1; i<size; i++)

{
item = list[i] ;
/* Move elements of list[0..i-1], that are greater than
item, to one position ahead of their current position */

for (j=i-1; (j>=0)&& (list[j] > item); j--)

list[j+1] = list[j];
list[j+1] = item ;
}
}

14
Lecture
CS 10001#07:
: Programming
© DSamantaand
Data Structures
Insertion Sort
int main()
{
int x[ ]={-45,89,-65,87,0,3,-23,19,56,21,76,-50};

int i;
for(i=0;i<12;i++)
printf("%d ",x[i]);
OUTPUT
printf("\n");
-45 89 -65 87 0 3 -23 19 56 21 76 -50
insertionSort(x,12);
-65 -50 -45 -23 0 3 19 21 56 76 87 89
for(i=0;i<12;i++)
printf("%d ",x[i]);
printf("\n");
}

15
CS 10001#07:
Lecture : Programming
© DSamantaand
Data Structures
Insertion Sort - Example

16
Lecture
CS 10001#07:
: Programming
© DSamantaand
Data Structures
Insertion Sort: Complexity Analysis

17
Lecture
CS 10001#07:
: Programming
© DSamantaand
Data Structures
Insertion Sort: Complexity analysis

18
Lecture
CS 10001#07:
: Programming
© DSamantaand
Data Structures
Insertion Sort: Complexity analysis

19
Lecture
CS 10001#07:
: Programming
© DSamantaand
Data Structures
Insertion Sort: Complexity analysis

20
Lecture
CS 10001#07:
: Programming
© DSamantaand
Data Structures
Insertion Sort: Complexity analysis

21
Lecture
CS 10001#07:
: Programming
© DSamantaand
Data Structures
Insertion Sort: Summary of Complexity Analysis
Case Comparisons Movement Memory Remarks
Case 1 Input list is in sorted
order
Case 2 Input list is sorted in
reverse order

Case 3 Input list is in random

order

Case Complexity Remarks

Case 1 Best case

Case 2 Worst case

Case 3 Average case

22
:

Selection Sort

23
Lecture
CS 10001#07:
: Programming
© DSamantaand
Data Structures
Selection Sort
General situation :
0 k size-1
x: smallest elements, sorted remainder, unsorted

Steps :
• Find smallest element, mval, in x[k…size-1]
• Swap smallest element with x[k], then increase k.

0 k mval size-1
x:

swap

24
Lecture
CS 10001#07:
: Programming
© DSamantaand
Data Structures
Selection Sort
/* Yield location of smallest element in
x[k .. size-1];*/

int findMinLloc (int x[ ], int k, int size)

{
int j, pos; /* x[pos] is the smallest
element found so far */
pos = k;
for (j=k+1; j<size; j++)
if (x[j] < x[pos])
pos = j;
return pos;
}

25
Lecture
CS 10001#07:
: Programming
© DSamantaand
Data Structures
Selection Sort
/* The main sorting function */
/* Sort x[0..size-1] in non-decreasing order */

int selectionSort (int x[], int size)

{ int k, m;
for (k=0; k<size-1; k++)
{
m = findMinLoc(x, k, size);
temp = a[k];
a[k] = a[m];
a[m] = temp;
}
}

26
Lecture
CS 10001#07:
: Programming
© DSamantaand
Data Structures
Selection Sort - Example
x: 14 -1 x: -1 14 4
3 12 -5 6 21 45 -5 3 6 12 21
2 7 7 2 5

x: -1 14 2 x: -1 14
12 -5 6 3 45 -5 3 6 12 21 45
7 2 1 7 2

x: -1 14 2 x: -1 14
-5 12 6 3 45 -5 3 6 12 21 45
7 2 1 7 2

x: -1 14 2
-5 3 6 12 45
7 2 1

x: -1 14
-5 3 6 21 12 45
7 2

x: -1 14
-5 3 6 12 21 45
7 2

27
Lecture
CS 10001#07:
: Programming
© DSamantaand
Data Structures
Selection Sort: Complexity Analysis

28
Selection Sort: Complexity Analysis

29
Lecture
CS 10001#07:
: Programming
© DSamantaand
Data Structures
Selection Sort: Complexity Analysis

30
Lecture
CS 10001#07:
: Programming
© DSamantaand
Data Structures
Selection Sort: Summary of Complexity analysis
Case Comparisons Movement Memory Remarks
Case 1 Input list is in sorted
order
Case 2 Input list is sorted in
reverse order

Case 3 Input list is in random

order

Case Complexity Remarks

Case 1 Best case

Case 2 Worst case

Case 3
Average case

31
:

Bubble Sort

32
Lecture
CS 10001#07:
: Programming
© DSamantaand
Data Structures
Bubble Sort
In every iteration The sorting process proceeds in
heaviest element drops
several passes.
at the bottom.
• In every pass we go on
comparing neighbouring pairs,
and swap them if out of order.
• In every pass, the largest of the
elements under considering
will bubble to the top (i.e., the
The bottom
moves upward. right).

33
Lecture
CS 10001#07:
: Programming
© DSamantaand
Data Structures
Bubble Sort

How the passes proceed?

• In pass 1, we consider index 0 to n-1.
• In pass 2, we consider index 0 to n-2.
• In pass 3, we consider index 0 to n-3.
• ……
• ……
• In pass n-1, we consider index 0 to 1.

34
Lecture
CS 10001#07:
: Programming
© DSamantaand
Data Structures
Bubble Sort - Example
Pass: 1

x: 3 1 -5 6 7 2 -7 4 x: 3 -5 6 1 7 2 -7 4
2 2 1 5 2 2 1 5

x: 3 1 -5 6 7 2 -7 4 x: 3 -5 6 1 2 7 -7 4
2 2 1 5 2 1 2 5

x: 3 -5 1 6 7 2 -7 4 x: 3 -5 6 1 2 -7 7 4
2 2 1 5 2 1 2 5

x: 3 -5 6 1 7 2 -7 4 x: 3 -5 6 1 2 -7 4 7
2 2 1 5 2 1 5 2

35
Lecture
CS 10001#07:
: Programming
© DSamantaand
Data Structures
Bubble Sort - Example
Pass: 2

x: 3 -5 6 1 2 -7 4 7 x: -5 3 6 1 2 -7 4 7
2 1 5 2 2 1 5 2

x: -5 3 6 1 2 -7 4 7 x: -5 3 6 1 -7 2 4 7
2 1 5 2 2 1 5 2

x: -5 3 6 1 2 -7 4 7 x: -5 3 6 1 -7 2 4 7
2 1 5 2 2 1 5 2

x: -5 3 6 1 2 -7 4 7
2 1 5 2

36
Lecture
CS 10001#07:
: Programming
© DSamantaand
Data Structures
Bubble Sort
void swap(int *x, int *y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}

void bubble_sort(int x[], int n)

{
int i,j;
for (i=n-1; i>0; i--)
for (j=0; j<i; j++)
if (x[j] > x[j+1])
swap(&x[j],&x[j+1]);
}

37
Lecture
CS 10001#07:
: Programming
© DSamantaand
Data Structures
Bubble Sort
int main()
{
int x[ ]={-45,89,-65,87,0,3,-23,19,56,21,76,-50};
int i;
for(i=0;i<12;i++)
printf("%d ",x[i]); OUTPUT
printf("\n");
-45 89 -65 87 0 3 -23 19 56 21 76 -50
bubble_sort(x,12);
for(i=0;i<12;i++) -65 -50 -45 -23 0 3 19 21 56 76 87 89
printf("%d ",x[i]);
printf("\n");
}

38
Lecture
CS 10001#07:
: Programming
© DSamantaand
Data Structures
Bubble Sort: Complexity analysis

39
Lecture
CS 10001#07:
: Programming
© DSamantaand
Data Structures
Bubble Sort: Complexity analysis

40
Lecture
CS 10001#07:
: Programming
© DSamantaand
Data Structures
Bubble Sort: Complexity analysis

41
Lecture
CS 10001#07:
: Programming
© DSamantaand
Data Structures
Bubble Sort: Complexity analysis

42
Lecture
CS 10001#07:
: Programming
© DSamantaand
Data Structures
Bubble Sort: Summary of Complexity analysis
Case Comparisons Movement Memory Remarks
Case 1 Input list is in sorted
order
Case 2 Input list is sorted in
reverse order

Case 3 Input list is in random

order

Case Complexity Remarks

Case 1 Best case

Case 2 Worst case

Case 3 Average case

43
Lecture
CS 10001#07:
: Programming
© DSamantaand
Data Structures
Bubble Sort

How do you make best case with (n-1)

comparisons only?

• By maintaining a variable flag, to check if

there has been any swaps in a given pass.
• If not, the array is already sorted.

44
Lecture
CS 10001#07:
: Programming
© DSamantaand
Data Structures
Bubble Sort
void bubble_sort(int x[], int n)
{
int i,j;
int flag = 0;
for (i=n-1; i>0; i--)
{
for (j=0; j<i; j++)
if (x[j] > x[j+1])
{
swap(&x[j],&x[j+1]);
flag = 1;
}
if (flag == 0) return;
}
}

45
Lecture
CS 10001#07:
: Programming
© DSamantaand
Data Structures
Efficient Sorting algorithms
Two of the most popular sorting algorithms are based on
divide-and-conquer approach.
• Quick sort
• Merge sort

Basic concept of divide-and-conquer method:

sort (list)
{
if the list has length greater than 1
{
Partition the list into lowlist and highlist;
sort (lowlist);
sort (highlist);
combine (lowlist, highlist);
}
}

46
Quick Sort

47
Lecture
CS 10001#07:
: Programming
© DSamantaand
Data Structures
Quick Sort – How it Works?
At every step, we select a pivot element in the list
(usually the first element).
• We put the pivot element in the final position of the sorted
list.
• All the elements less than or equal to the pivot element are
to the left.
• All the elements greater than the pivot element are to the
right.

48
Lecture
CS 10001#07:
: Programming
© DSamantaand
Data Structures
Quick Sort Partitioning
0 size-1
x:
pivot

Values smaller Values greater

Perform Perform
partitioning partitioning

49
Lecture
CS 10001#07:
: Programming
© DSamantaand
Data Structures Quick Sort
#include <stdio.h>
void quickSort( int[], int, int);
int partition( int[], int, int);
void main()
{
int i,a[] = { 7, 12, 1, -2, 0, 15, 4, 11, 9};
printf("\n\nUnsorted array is: ");
for(i = 0; i < 9; ++i)
printf(" %d ", a[i]);
quickSort( a, 0, 8);
printf("\n\nSorted array is: ");
for(i = 0; i < 9; ++i)
printf(" %d ", a[i]);
}
void quickSort( int a[], int l, int r)
{
int j;
if( l < r ) { // divide and conquer
j = partition( a, l, r);
quickSort( a, l, j-1);
quickSort( a, j+1, r);
}
}

50
Lecture
CS 10001#07:
: Programming
© DSamantaand
Data Structures
Quick Sort
int partition( int a[], int l, int r)
{
int pivot, i, j, t;
pivot = a[l];
i = l;
j = r+1;
while( 1) {
do {
++i;
} while(a[i]<=pivot && i<=r);
do {
--j;
} while( a[j] > pivot );
if( i >= j ) break;
t = a[i];
a[i] = a[j];
a[j] = t;
}
t = a[l];
a[l] = a[j];
a[j] = t;
return j;
}

51
CS 10001#07:
Lecture : Programming
© DSamantaand
Data Structures
Quick Sort - Example
Input: 45 -56 78 90 -3 -6 123 0 -3 45 69 68

45 -56 78 90 -3 -6 123 0 -3 45 69 68

-6 -56 -3 0 -3 45 123 90 78 45 69 68
-
-56 -3 0 -3 68 90 78 45 69 123
6
-
0 -3 45 68 78 90 69
3
-3 0 69 78 90

Output: -56 -6 -3 -3 0 45 45 68 69 78 90 123

52
Lecture
CS 10001#07:
: Programming
© DSamantaand
Data Structures
Quick Sort: Complexity analysis

53
Lecture
CS 10001#07:
: Programming
© DSamantaand
Data Structures
Quick Sort: Complexity analysis

54
Lecture
CS 10001#07:
: Programming
© DSamantaand
Data Structures
Quick Sort: Complexity analysis

55
Lecture
CS 10001#07:
: Programming
© DSamantaand
Data Structures
Quick Sort: Complexity analysis

(i-1) (n-1)

56
Lecture
CS 10001#07:
: Programming
© DSamantaand
Data Structures
Quick Sort: Complexity analysis

57
Lecture
CS 10001#07:
: Programming
© DSamantaand
Data Structures
Quick Sort: Summary of Complexity analysis
Case Comparisons Movement Memory Remarks
Case 1 Input list is in sorted
order
Case 2 Input list is sorted in
reverse order
Case 3 Input list is in
random order

Case Complexity Remarks

Case 1 Worst case

Case 2
Worst case

Case 3 Best / Average

case

58
Merge Sort

59
:

Merge Sort – How it Works?

Input Array

Part-I Part-II

Part-I Part-II Part-I Part-II

Split
Merge
Sorted arrays

60
Lecture
CS 10001#07:
: Programming
© DSamantaand
Data Structures
Merging two Sorted arrays

a: Sorted Array b: Sorted Array

0 l 0 m

c: Merged sorted array

0 l+m-1

61
Lecture
CS 10001#07:
: Programming
© DSamantaand
Data Structures
Merge Sort – Example
x: 3 1 -5 6 7 2 -7 4
2 2 1 5
1 7 2 4
3 -5 6 Splitting arrays -7
2 2 1 5
1 7 2 4
3 -5 6 -7
2 2 1 5
1 7 2 4
3 -5 6 -7
2 2 1 5
1 2 7 4
3 -5 6 -7
2 1 2 5
1 Merging two 2 4 7
-5 3 6 -7
2 sorted arrays 1 5 2

1 2 4 7
-7
-7 -5 3 6
2 1 5 2 62
Lecture
CS 10001#07:
: Programming
© DSamantaand
Data Structures Merge Sort Program
#include<stdio.h>
void mergesort(int a[],int i,int j);
void merge(int a[],int i1,int j1,int i2,int j2);
int main()
{
int a[30],n,i;
printf("Enter no of elements:");
scanf("%d",&n);
printf("Enter array elements:");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
mergesort(a,0,n-1);
printf("\nSorted array is :");
for(i=0;i<n;i++)
printf("%d ",a[i]);
return 0;
}
63
Lecture
CS 10001#07:
: Programming
© DSamantaand
Data Structures Merge Sort Program

void mergesort(int a[],int i,int j)

{
int mid;

if(i<j) {
mid=(i+j)/2;
/* left recursion */
mergesort(a,i,mid);
/* right recursion */
mergesort(a,mid+1,j);
/* merging of two sorted sub-arrays */
merge(a,i,mid,mid+1,j);
}
}

64
Lecture
CS 10001#07:
: Programming
© DSamantaand
Data Structures Merge Sort Program
void merge(int a[],int i1,int i2,int j1,int j2)
{
int temp[50]; //array used for merging
int i=i1,j=j1,k=0;
while(i<=i2 && j<=j2) //while elements in both lists
{
if(a[i]<a[j])
temp[k++]=a[i++];
else
temp[k++]=a[j++];
}
while(i<=i2) //copy remaining elements of the first list
temp[k++]=a[i++];
while(j<=j2) //copy remaining elements of the second list
temp[k++]=a[j++];
for(i=i1,j=0;i<=j2;i++,j++)
a[i]=temp[j]; //Transfer elements from temp[] back to a[]
}

65
Lecture
CS 10001#07:
: Programming
© DSamantaand
Data Structures Merge Sort – Splitting Trace
-56 23 43 -5 -3 0 123 -35 87 56 75 80

-56 23 43 -5 -3 0 123 -35 87 56 75 80

-56 23 43 -5 -3 0 123 -35 87 56 75 80

-56 23 43 -5 -3 0 123 -35 87 56 75 80

23 43 -3 0 -35 87 75 80

Output: -56 -35 -5 -3 0 23 43 56 75 80 87 123

Space Complexity?? Worst Case: O([Link](n))

66
Merge Sort: Complexity analysis

67
Lecture
CS 10001#07:
: Programming
© DSamantaand
Data Structures
Quick Sort vs. Merge Sort
• Quick sort
• hard division, easy combination
• partition in the divide step of the divide-and-conquer
framework
• hence combine step does nothing

• Merge sort
• easy division, hard combination
• merge in the combine step
• the divide step in this framework does one simple
calculation only

68
Lecture
CS 10001#07:
: Programming
© DSamantaand
Data Structures
Quick Sort vs. Merge Sort
Both the algorithms divide the problem into two sub
problems.
• Merge sort:
– two sub problems are of almost equal size always.

• Quick sort:
– an equal sub division is not guaranteed.

• This difference between the two sorting methods appears as

the deciding factor of their run time performances.

69
Different Comparison based sorting algorithms
Sorting Worst-case Best-case Space
Algorithm time time overhead
Selection sort Ο (n2) Ο(n2) Ο(1)

Bubble Sort Ο (n2) Ο (n) Ο(1)

Insertion Ο (n2) Ο (n) Ο(1)

Sort
Merge Sort Ο (n log n) Ο (n log n) Ο(n)

Quick Sort Ο (n2) Ο (n log n) Ο(1)

72
Heap Sort : REVIEW
A sorting algorithm that works by first organizing the data to be
sorted into a special type of binary tree called a heap
Procedures on Heap
• Heapify
• Build Heap
• Heap Sort
Heapify
• Heapify picks the largest child key and compare it to the parent key.
If parent key is larger than heapify quits, otherwise it swaps the
parent key with the largest child key. So that the parent is now
becomes larger than its children.
Heapify(A, i)
{
l left(i)
r right(i)
if l <= heapsize[A] and A[l] > A[i]
then largest l
else largest i
if r <= heapsize[A] and A[r] > A[largest]
then largest r
if largest != i
then swap A[i] A[largest]
Heapify(A, largest)
}
Build Heap
• We can use the procedure 'Heapify' in a bottom-up fashion to
convert an array A[1 . . n] into a heap. Since the elements in the
subarray A[n/2 +1 . . n] are all leaves, the procedure BUILD_HEAP
goes through the remaining nodes of the tree and runs 'Heapify' on
each one. The bottom-up order of processing node guarantees that
the subtree rooted at children are heap before 'Heapify' is run at
their parent.

Buildheap(A)
{
heapsize[A] length[A]
for i |length[A]/2 //down to 1
do Heapify(A, i)
}
Heap Sort Algorithm
• The heap sort algorithm starts by using procedure BUILD-HEAP to
build a heap on the input array A[1 . . n]. Since the maximum
element of the array stored at the root A[1], it can be put into its
correct final position by exchanging it with A[n] (the last element in
A). If we now discard node n from the heap than the remaining
elements can be made into heap. Note that the new element at the
root may violate the heap property. All that is needed to restore the
heap property.

Heapsort(A)
{
Buildheap(A)
for i length[A] //down to 2
do swap A[1] A[i]
heapsize[A] heapsize[A] - 1
Heapify(A, 1)
}
Example: Convert the following array to a heap

16 4 7 1 12 19

Picture the array as a complete binary tree:

16

4 7

1 12 19
 16 16

4 7 4 19
swap

12 19 1 12 7
1

16 19
swap

12 19 12 16
swap

4 7 1 4 7
1
Heap Sort
• The heapsort algorithm consists of two phases:
- build a heap from an arbitrary array
- use the heap to sort the data

• To sort the elements in the decreasing order, use a min heap

• To sort the elements in the increasing order, use a max heap

19

12 16

1 4 7
Example of Heap Sort
Take out biggest
19

12 16
Move the last element
to the root

1 4 7

Sorted:
Array A

12 16 1 4 7 19
 7
swap
HEAPIFY()
12 16

1 4

Sorted:
Array A

7 12 16 1 4 19
 16

12 7

1 4

Sorted:
Array A

16 12 7 1 4 19
 Take out biggest
16
Move the last element
to the root
12 7

1 4

Sorted:
Array A

12 7 1 4 16 19
 4

12 7

Sorted:
Array A

4 12 7 1 16 19
 swap 4

HEAPIFY()
12 7

Sorted:
Array A

4 12 7 1 16 19
 12

4 7

Sorted:
Array A

12 4 7 1 16 19
 Take out biggest
12
Move the last
element to the
root 4 7

Sorted:
Array A

4 7 1 12 16 19
 1
swap

4 7

Sorted:
Array A

1 4 7 12 16 19
 7

4 1

Sorted:
Array A

7 4 1 12 16 19
 Take out biggest
7
Move the last
element to the
4 1 root

Sorted:
Array A

1 4 7 12 16 19
 swap 1

HEAPIFY()
4

Sorted:
Array A

4 1 7 12 16 19
 Take out biggest
Move the last 4
element to the
root
1

Sorted:
Array A

1 4 7 12 16 19
 Take out biggest
1

Sorted:
Array A

1 4 7 12 16 19
 Sorted:

1 4 7 12 16 19
Time Analysis
• Build Heap Algorithm will run in O(n) time
• There are n-1 calls to Heapify each call requires O(log n)
time
• Heap sort program combine Build Heap program and
Heapify, therefore it has the running time of O(n log n) time
• Total time complexity: O(n log n)
How Fast Can We Sort?

• Selection Sort, Bubble Sort, Insertion Sort:

O(n2)
• Heap Sort, Merge sort: O(nlgn)
• Quicksort: O(nlgn) - average
• What is common to all these algorithms?
• Make comparisons between input elements

a i < a j, a i ≤ a j, a i = a j, a i ≥ a j, or ai > a j

97
Can we do better?
• Linear sorting algorithms – Non- comparison based algorithm
• Counting Sort
• Radix Sort
• Bucket sort
• Make certain assumptions about the data
• Can sort in O(n) time

98
Counting Sort
• Assumptions:
• n integers which are in the range [0 ... r]
• r is in the order of n, that is, r=O(n)
• Idea:
• For each element x, find the number of elements x
• Place x into its correct position in the output array

output array

99
Step 1
(i.e., frequencies)

(r=6)

100
Step 2

C (frequencies) Cnew (cumulative sums)

101
Algorithm
• Start from the last element of A
• Place A[i] at its correct place in the output array
• Decrease C[A[i]] by one
1 2 3 4 5 6 7 8

A 2 5 3 0 2 3 0 3
0 1 2 3 4 5

Cnew 2 2 4 7 7 8
Example
1 2 3 4 5 6 7 8 0 1 2 3 4 5

A 2 5 3 0 2 3 0 3 Cnew 2 2 4 7 7 8

1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8

B 3 B 0 3
0 1 2 3 4 5
0 1 2 3 4 5

C new
2 2 4 6 7 8 Cnew 1 2 4 6 7 8

1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8

B 0 3 3 B 0 2 3 3
0 1 2 3 4 5
0 1 2 3 4 5

C new
1 2 4 5 7 8 Cnew 1 2 3 5 7 8
103
Example (cont.)
1 2 3 4 5 6 7 8

A 2 5 3 0 2 3 0 3

1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8

B 0 0 2 3 3 B 0 0 2 3 3 3 5
0 1 2 3 4 5 0 1 2 3 4 5

C 0 2 3 5 7 8 C 0 2 3 4 7 7

1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8

B 0 0 2 3 3 3 B 0 0 2 2 3 3 3 5
0 1 2 3 4 5

C 0 2 3 4 7 8

104
COUNTING-SORT
1 j n

A
Alg.: COUNTING-SORT(A, B, n, k) 0 k

1. for i ← 0 to r C
2. do C[ i ] ← 0 1 n

B
3. for j ← 1 to n
4. do C[A[ j ]] ← C[A[ j ]] + 1
5. C[i] contains the number of elements equal to i
6. for i ← 1 to r
7. do C[ i ] ← C[ i ] + C[i -1]
8. C[i] contains the number of elements ≤ i
9. for j ← n downto 1
10. do B[C[A[ j ]]] ← A[ j ]
11. C[A[ j ]] ← C[A[ j ]] - 1
105
 Analysis of Counting Sort
Alg.: COUNTING-SORT(A, B, n, k)
1. for i ← 0 to r O(r)
2. do C[ i ] ← 0
3. for j ← 1 to n
O(n)
4. do C[A[ j ]] ← C[A[ j ]] + 1
5. C[i] contains the number of elements equal to i
6. for i ← 1 to r
O(r)
7. do C[ i ] ← C[ i ] + C[i -1]
8. C[i] contains the number of elements ≤ i
9. for j ← n downto 1
10. do B[C[A[ j ]]] ← A[ j ] O(n)
11. C[A[ j ]] ← C[A[ j ]] - 1

Overall time: O(n + r) 106

Analysis of Counting Sort
• Overall time: O(n + r)

• In practice we use COUNTING sort when r = O(n)

⇒ running time is O(n)

Analysis of Counting Sort
• Overall time: O(n + r)

• In practice we use COUNTING sort when r = O(n)

⇒ running time is O(n)

Radix Sort
• Represents keys as d-digit numbers in some base-k
key = x1x2...xd where 0≤xi≤k-1
• Example: key=15
key10 = 15, d=2, k=10 where 0≤xi≤9

key2 = 1111, d=4, k=2 where 0≤xi≤1

111
Radix Sort
• Assumptions
d=O(1) and k =O(n)
• Sorting looks at one column at a time
• For a d digit number, sort the least significant
digit first
• Continue sorting on the next least significant digit,
until all digits have been sorted
• Requires only d passes through the list

112
RADIX-SORT
Alg.: RADIX-SORT(A, d)
for i ← 1 to d
do use a stable sort to sort array A on digit i

(stable sort: preserves order of identical elements)

113
Analysis of Radix Sort
• Given n numbers of d digits each, where each digit may take up to k

possible values, RADIX-SORT correctly sorts the numbers in O(d(n+k))

• One pass of sorting per digit takes O(n+k) assuming that we use counting sort

• There are d passes (for each digit)

114
Analysis of Radix Sort
• Given n numbers of d digits each, where each digit may take up to k

possible values, RADIX-SORT correctly sorts the numbers in

O(d(n+k))

• Assuming d=O(1) and k=O(n), running time is O(n)

115
References
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to
Algorithms (3rd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03384-4.
• Alfred V. Aho, J.E. Hopcroft, Jeffrey D. Ullman, Data Structures and Algorithms, Addison-Wesley Series in
Computer Science and Information Processing, 1983
• [Link]
• [Link]
• [Link]
• [Link]
• [Link]

116