Disclaimer: Original

course by Dr.

SORTING ALGORITHMS Rajasekaranm, Dr.

David A. Plaisted and
other references.
 SORTING
• Insert sort
• Selection sort

ALGORITHMS • Heap sort

SORTING ALGORITHMS
• Sorting algorithms are fundamental techniques in computer science
used to arrange data elements into a particular order—most
commonly in ascending or descending sequence.

• The efficiency of many computational processes depends on the

ability to sort data quickly and accurately.
SORTING ALGORITHMS
An internal sort is a sorting algorithm that works entirely in main memory (RAM).
That means all the data to be sorted fits into memory at once.
▪ Examples: Insertion Sort, Merge Sort (in-memory), Quick Sort.

▪ Use case: When the dataset is small or moderate in size and can be stored in
RAM.
▪ Characteristics:
▪ Faster (no disk I/O).
▪ Simpler to implement.
▪ Limited by the amount of available memory.

▪ Example: Sorting 10,000 integers in an array using quicksort — all stored in

memory.
SORTING ALGORITHMS
An external sort is used when the dataset is too large to fit into main memory and
must be stored on external storage such as a hard drive or SSD.
The algorithm processes the data in chunks (blocks), reading and writing between
memory and disk.
▪ Examples: External Merge Sort, External Quick Sort.

▪ Use case: Very large files, databases, or big data systems.

▪ Characteristics:
▪ Involves disk I/O operations (slower).
▪ Needs careful design to minimize read/write operations.

▪ Example: Sorting a 100 GB log file stored on disk.

SORTING ALGORITHMS
An in-place sorting algorithm sorts data without using extra memory proportional
to the size of the input — it only uses a constant amount of extra space (O(1)).
▪ Examples: Insertion Sort, Selection Sort, Heap Sort.

▪ Characteristics:
▪ Efficient in terms of space.
▪ May overwrite the original array.

▪ Example: Insertion Sort shifts elements within the same array — it doesn’t create
a new one.
INSERTION SORT
𝑨𝒍𝒈𝒐𝒓𝒊𝒕𝒉𝒎: 𝑰𝑵𝑺𝑬𝑹𝑻𝑰𝑶𝑵𝑺𝑶𝑹𝑻
𝑰𝒏𝒑𝒖𝒕: 𝐴𝑛 𝑎𝑟𝑟𝑎𝑦 𝐴[1. . 𝑛] 𝑜𝑓 𝑛 𝑒𝑙𝑒𝑚𝑒𝑛𝑡𝑠.
𝑶𝒖𝒕𝒑𝒖𝒕: 𝐴[1. . 𝑛] 𝑠𝑜𝑟𝑡𝑒𝑑 𝑖𝑛 𝑛𝑜𝑛 − 𝑑𝑒𝑐𝑟𝑒𝑎𝑠𝑖𝑛𝑔 𝑜𝑟𝑑𝑒𝑟.

1. 𝒇𝒐𝒓 𝑖 = 1 𝒕𝒐 𝑛 − 1 // i start from the second element

2. 𝑥 = 𝐴[𝑖] // element assignments in blue
3. 𝑗 = 𝑖 − 1
4. 𝒘𝒉𝒊𝒍𝒆 (𝑗 ≥ 0) 𝒂𝒏𝒅 (𝐴[𝑗] > 𝑥) // while j ≠ null
5. 𝐴[𝑗 + 1] = 𝐴[𝑗]
6. 𝑗 = 𝑗 − 1
7. 𝒆𝒏𝒅 𝒘𝒉𝒊𝒍𝒆
8. 𝐴[𝑗 + 1] = 𝑥
9. 𝒆𝒏𝒅 𝒇𝒐𝒓
INSERT SORT EXAMPLE
6 2 11 7
▪ For i=1, (unsorted array)
j i
x= A[i] ➔ A[1]= 2→ x=2
j= i-1 ➔ j= 0
while (j ≥ 0) and (A[j] > x) 6 6 11 7
A[j + 1] = A[j] ➔ A[1] = A[0] j i

j=j–1 ➔ j= null ➔ end while loop

2 6 11 7
A[j + 1] = x ➔ A[0] = 2

▪ For i=2
2 6 11 7
x= A[i] ➔ A[2]= 11 → x=11
j i
j= i-1 ➔ j= 1
while (j ≥ 0) and (A[j] > x) end while loop

▪ For i=3
2 6 11 7
x= A[i] ➔ A[3]= 7→ x=7 j i
j= i-1 ➔ j= 2
while (j ≥ 0) and (A[j] > x)
A[j + 1] = A[j] ➔ A[3] = A[2] 2 6 11 11
j i
j=j–1 → j=1
2 6 7 11
A[j + 1] = x ➔ A[2] = 7 ➔ continue while loop, j=1→ (A[j1] < x) exit while loop

2 6 7 11
▪ For i=4 End for
j i
INSERT SORT– ANALYSIS
▪ The number of element comparisons done by Algorithm insertion sort depends
on the order of the input elements.
▪ It is easy to see that the number of element comparisons is minimum when the array is
already sorted in nondecreasing order.

▪ Performance depends on the number of element comparisons = relative

ordering of the input elements
▪ The minimum number of element comparisons is 𝒏 − 𝟏 which occurs when the array is sorted (best
case)
𝒏(𝒏−𝟏)
▪ The maximum number of element comparisons is which occurs when the array is sorted in
𝟐
𝒏(𝒏−𝟏)
reverse order and all element are distinct (worst case) = σ𝒏−𝟏
𝒊=𝟏 𝒊 = = 𝑶(𝒏𝟐 )
𝟐
 SELECTION SORT
▪ Let A[1…n] be an array of n elements.
▪ The list is divided into two sub-lists, sorted and unsorted, which are divided by an
imaginary wall.
▪ We find the smallest element from the unsorted sub-list and swap it with the
element at the beginning of the unsorted data.
▪ A list of n elements requires n-1 passes to completely rearrange the data.
▪ After each selection and swapping, the imaginary wall between the two sub-lists
move one element ahead, increasing the number of sorted elements and decreasing
the number of unsorted ones.
▪ Each time we move one element from the unsorted sub-list to the sorted sub-list,
we say that we have completed a sort pass.

▪ A simple and straightforward algorithm to sort the entries in A works as follows.

▪ First, we find the minimum element and store it in A[1].
▪ Next, we find the minimum of the remaining n-1 elements and store it in A[2].
▪ We continue this way until the second largest element is stored in A[n-1].
▪ This method is described in Algorithm selection-sort.
▪ It is easy to see that the number of element comparisons performed by the algorithm is exactly
𝒏−𝟏 𝒏−𝟏
𝒏(𝒏 − 𝟏)
෍ 𝒏 − 𝒊 = 𝒏 − 𝟏 + 𝒏 − 𝟐 + … . . +𝟏 = ෍ 𝒊 =
𝟐
𝒊=𝟏 𝒊=𝟏
▪ Observation: the number of comparisons performed by Algorithm selection sort is exactly 𝑛 𝑛 − 1 = 𝑛2 regardless of how the
elements of the input array are ordered
SELECTION SORT
▪ For i=0, k=0, j= 1(unsorted array)
6 2 11 7
i, k j
Algorithm SELECTIONSORTRE
▪ If A[j] < A[k] then k=j ➔ A[1] < A[0] ➔ yes, then k=1, j++ ➔ j=2
Input: An array A[1..n] of n elements.
Output: A[1..n] sorted in nondecreasing order
6 2 11 7
➔
i k j
1. for i← 1 to n-1 The outer for loop executes n-1
times
▪ If A[j] < A[k] then k=j ➔ A[2] < A[1] ➔ no, then, j++ ➔ 3 2. k← i
➔ 3. for j← i+1 to n //{find the ith smallest element}
6 2 11 7
i k j

▪ If A[j] < A[k] then k=j ➔ A[3] < A[1] ➔ no, then, j++ ➔ 4 4. if A[j] < A[k] then k ← j;
end inner loop 5. end for
▪ If k ≠ i then swap(A[i], A[k]) ➔ A[0] <= A[1] 6. if k ≠ i then Swap(A[i], A[k]);
▪ For i=1, k=1, j= 2(unsorted array) 7. end for

Sorted subarray Unsorted subarray

2 6 11 7
i,k j
▪ Repeat
SELECTION SORT – ANALYSIS
▪ The inner for loop executes the size of the unsorted part minus 1 (from 1 to n-1),
and in each iteration we make one key comparison.
➔ # of key comparisons = 1+2+...+n-1 = n*(n-1)/2
➔ So, Selection sort is O(n2)

▪ The best case, the worst case, and the average case of the selection sort algorithm
are same. ➔ all of them are O(n2)
▪ This means that the behavior of the selection sort algorithm does not depend on the
initial organization of data.
▪ Since O(n2) grows so rapidly, the selection sort algorithm is appropriate only for small n.
REMARKS ON SELECTION SORT AND
INSERTION SORT ALGORITHMS:
▪ The number of element comparisons in INSERTIONSORT is sensitive to the
relative ordering of the array elements which is not the case
SELECTIONSORT.
▪ Unlike Algorithm selection sort, the number of element comparisons done by
Algorithm insertion sort depends on the order of the input elements
▪ Insertion sort and selection sort are both inefficient as the number of
operations required to sort n elements is proportional to 𝑛2 in the worst case.
HEAP SORT
HEAP SORT
▪ Heap is an ordered complete binary tree

▪ Max heap: key parent >= children

HEAP SORT ALGORITHM
Given an unsorted list, for example unsorted array A[]:
▪ Build the Max Heap Transform the unsorted array into a valid max-heap where
the largest element is at the root.
▪ Swap the Root with the Last Element.

▪ Reduce the Heap Size by 1: Exclude the last element, after swapping, from the
heap portion of the array.
▪ Heapify the Root: Restore the max-heap property by applying heapify() from the
root downward.
▪ Repeat Steps 2–4 Continue until all elements are sorted.
EXAMPLE
2
Given unsorted array A[]:

2 8 5 3 9 1
8 5

3 9 1

ARRAY TREE
Step1, we build the max heap. Convert the unsorted array into a Max-Heap, where the largest
element is at the root

2 8 5 3 9 1 9 8 5 3 2 1

2 9

8 5 8 5
Build Max Heap

3 9 1 3 2 1

TREE Max Heap

 Step2, swap the root with the last element in the max heap

9 8 5 3 2 1 1 8 5 3 2 9

9 1

8 5 8 5

3 2 1 3 2 9

Max Heap
Sep 3, Reduce the Heap Size by 1 and consider 9 sorted
in the array

1 8 5 3 2 9
Heap portion
Sorted part

8 5

3 2
 Sep 4, 1 now is out of its place, so, we call heapify to
restore max heap order property

1 8 5 3 2 9 8 3 5 1 2 9

1 8 8

heapify
8 5 1 5 3 5

3 2 3 2 1 2
 Repeat step 2 ,3, 4 until only one element remains
unsorted (until the array sorted)
After restoring the max heap property, again, swap the
root with the last element in the max heap

8 3 5 1 2 9 2 3 5 1 8 9

8 2

3 5 3 5

1 2 1 8

Max Heap
Reduce the Heap Size by 1 and consider 8 sorted in the
array

2 3 5 1 8 9
Heap portion Sorted part

3 5

1
 2 now is out of its place, so, we call heapify to restore
max heap order property

2 3 5 1 8 9 5 3 2 1 8 9

2 5

heapify
3 5 3 2

1 1
5 3 2 1 8 9 1 3 2 5 8 9 1 3 2 5 8 9
Heap portion Sorted part

5 1 1

3 2 3 2 3 2

1 5

Max Heap
1 3 2 5 8 9 3 1 2 5 8 9

1 3
heapify

3 2 1 2
3 1 2 5 8 9 2 1 3 5 8 9 2 1 3 5 8 9
Heap portion Sorted part

3 2 2

1 2 1 3 1

Max Heap
2 1 3 5 8 9 2 1 3 5 8 9

2 heapify 2

1 1
2 1 3 5 8 9 1 2 3 5 8 9 1 2 3 5 8 9
Sorted part
Heap portion

2 1 1

1 2

Max Heap

1 2 3 5 8 9
Sorted array
 HEAP SORT PSEUDOCODE
Procedure HEAPSORT(A) Procedure BUILD_MAX_HEAP(A)
BUILD_MAX_HEAP(A) heap_size ← length(A)
for i ← length(A) downto 2 do for i ← floor(heap_size / 2) downto 1 do
swap A[1] A[i] // move current max to end HEAPIFY(A, i)
heap_size ← heap_size - 1 end for
HEAPIFY(A, 1) End Procedure Procedure HEAPIFY(A, i)
end for left ← 2 * i
End Procedure right ← 2 * i + 1

if (left ≤ heap_size) and (A[left] > A[i]) then

largest ← left
else
largest ← i
end if

if (right ≤ heap_size) and (A[right] > A[largest]) then

largest ← right
end if

if (largest ≠ i) then
swap A[i] A[largest]
HEAPIFY(A, largest)
end if
End Procedure
HEAP SORT PERFORMANCE
▪ Time Complexity of Heap sort is O(n log n)
▪ Building the max heap takes O(n)
▪ Each Heapify operation takes O(log n), and it is applied repeatedly for (n−1)
elements during sorting, resulting in an overall time complexity of O(n log n).

▪ Heap sort is in-place algorithm, it has space complexity of O(1)

(Because the heap is stored in the same array)