Skip to content
CampusPrep
AD-303 · Data Structures/Quick Revision Short Notes

Data Structures (AD-303) - Unit 5 Short Notes

How unit 5 is examined

Sorting, searching, hashing and indexing; hashing, sorting comparison, quick, heap and merge sort carry the marks.

Introduction

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. <mark>Sorting arranges a list in ascending or descending key order, and searching finds the position of a given key in a list.</mark>

Key points.

  1. Internal sorting works in memory, external sorting on disk; comparison sorts cannot beat $O(n \log n)$ in the worst case.

Bubble Sort

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. <mark>Bubble sort repeatedly compares adjacent elements and swaps them if they are out of order, so the largest element bubbles to the end in each pass.</mark>

Key points.

  1. It needs $n-1$ passes, and after pass $i$ the last $i$ elements are final.
  2. Comparisons total $n(n-1)/2$, so time is $O(n^2)$; a no-swap flag gives $O(n)$ best case.
  3. It is stable and in place.

Quick sort

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>

Definition. <mark>Quick sort is a divide-and-conquer method that picks a pivot, partitions the array so smaller elements lie left and larger lie right of the pivot, and then sorts both parts recursively.</mark>

Key points.

  1. With the first element as pivot, $i$ moves right past elements $\le$ pivot and $j$ moves left past elements $>$ pivot.
  2. If both stop with $i<j$, swap $a[i]$, $a[j]$; when they cross, swap the pivot with $a[j]$, fixing its place, and sort both sides recursively.
  3. Best and average time is $O(n \log n)$; worst is $O(n^2)$, for sorted input with an end pivot.
  4. Extra space is $O(\log n)$ for the stack; it is in place but not stable.

Example. Bold is the fixed pivot; "cross" means $i>j$, so the pivot swaps with $a[j]$.

Sub-array $i$, $j$ stops Result
36,25,32,5,8,65,38,47,95 $i$ 65, $j$ 8, cross 8,25,32,5,36,65,38,47,95
8,25,32,5 $i$ 25, $j$ 5, swap: 8,5,32,25; $i$ 32, $j$ 5, cross 5,8,32,25
32,25 $i$ past end, $j$ 25, cross 25,32
65,38,47,95 $i$ 95, $j$ 47, cross 47,38,65,95
47,38 $i$ past end, $j$ 38, cross 38,47

Sorted: 5,8,25,32,36,38,47,65,95.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u5-01" viewBox="0 0 448 262" width="448" height="262" role="img" aria-label="Recursion tree, each node is the pivot fixed by one partition"><style>#dsfig-u5-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u5-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u5-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u5-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u5-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u5-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u5-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u5-01 .t{fill:#16181D;font-weight:500}#dsfig-u5-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u5-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u5-01 .dot{fill:#16181D}#dsfig-u5-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u5-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u5-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u5-01 .ah{fill:#454C5A}#dsfig-u5-01 .ah.hi{fill:#2340B8}#dsfig-u5-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u5-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u5-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u5-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u5-01 .e{stroke:#B1B7C3}html.dark #dsfig-u5-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u5-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u5-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u5-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u5-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u5-01 .t{fill:#E6E8ED}html.dark #dsfig-u5-01 .t.inv{fill:#0F1115}html.dark #dsfig-u5-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u5-01 .dot{fill:#E6E8ED}html.dark #dsfig-u5-01 .ann{fill:#8FA3FF}html.dark #dsfig-u5-01 .lbl{fill:#858D9C}html.dark #dsfig-u5-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u5-01 .ah{fill:#B1B7C3}html.dark #dsfig-u5-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u5-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u5-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u5-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah50" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh50" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="212" y1="39" x2="80" y2="103"/><line class="e" x1="212" y1="39" x2="344" y2="103"/><line class="e" x1="80" y1="103" x2="36" y2="167"/><line class="e" x1="80" y1="103" x2="168" y2="167"/><line class="e" x1="168" y1="167" x2="124" y2="231"/><line class="e" x1="344" y1="103" x2="300" y2="167"/><line class="e" x1="344" y1="103" x2="388" y2="167"/><line class="e" x1="300" y1="167" x2="256" y2="231"/><circle class="n" cx="212" cy="39" r="17"/><text class="t" x="212" y="39" dy=".35em" text-anchor="middle">36</text><circle class="n" cx="80" cy="103" r="17"/><text class="t" x="80" y="103" dy=".35em" text-anchor="middle">8</text><circle class="n" cx="36" cy="167" r="17"/><text class="t" x="36" y="167" dy=".35em" text-anchor="middle">5</text><circle class="n" cx="168" cy="167" r="17"/><text class="t" x="168" y="167" dy=".35em" text-anchor="middle">32</text><circle class="n" cx="124" cy="231" r="17"/><text class="t" x="124" y="231" dy=".35em" text-anchor="middle">25</text><circle class="n" cx="344" cy="103" r="17"/><text class="t" x="344" y="103" dy=".35em" text-anchor="middle">65</text><circle class="n" cx="300" cy="167" r="17"/><text class="t" x="300" y="167" dy=".35em" text-anchor="middle">47</text><circle class="n" cx="256" cy="231" r="17"/><text class="t" x="256" y="231" dy=".35em" text-anchor="middle">38</text><circle class="n" cx="388" cy="167" r="17"/><text class="t" x="388" y="167" dy=".35em" text-anchor="middle">95</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Recursion tree, each node is the pivot fixed by one partition</figcaption></figure>

Step 1: Partition(a,lo,hi): p=a[lo], i=lo, j=hi+1.
Step 2: repeat i++ while i<=hi and a[i]<=p; repeat j-- while a[j]>p.
Step 3: if i<j swap a[i], a[j] and go to Step 2; else swap a[lo], a[j] and return j.
Step 4: QuickSort: if lo<hi: k=Partition(lo,hi); sort lo..k-1 and k+1..hi.

Balanced: $T(n)=2T(n/2)+n=O(n \log n)$; one-sided: $T(n)=T(n-1)+n=O(n^2)$, avoided by a median-of-three pivot.

Second list, 44,33,11,55,77,90,40,60,99,22,88,66:

Sub-array $i$, $j$ stops Result
whole list $i$ 55, $j$ 22, swap; $i$ 77, $j$ 40, swap; $i$ 90, $j$ 40, cross 40,33,11,22,44,90,77,60,99,55,88,66
40,33,11,22 $i$ past end, $j$ 22, cross 22,33,11,40
22,33,11 $i$ 33, $j$ 11, swap; cross at 11 11,22,33
90,77,60,99,55,88,66 $i$ 99, $j$ 66, swap; $i$ 99, $j$ 88, cross 88,77,60,66,55,90,99
88,77,60,66,55 $i$ past end, $j$ 55, cross 55,77,60,66,88
55,77,60,66 $j$ stops on 55, no move; then 77 and 66 each swap with $a[j]$ 55,60,66,77

Sorted: 11,22,33,40,44,55,60,66,77,88,90,99.

Answer frame. Open with the definition; write the partition steps, the trace table and the recursion tree; state the cases; close with "fast but unstable".

Asked: [7 marks] (Dec 2022) Sort using quick sort algorithm: 36, 25, 32, 5, 8, 65, 38, 47, 95. Also sort 44, 33, 11, 55, 77, 90, 40, 60, 99, 22, 88, 66. Asked: [7 marks] (Dec 2025) Explain the Quick Sort algorithm with suitable example.

Selection sort

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>

Definition. <mark>Selection sort repeatedly selects the minimum element of the unsorted part and swaps it with the first unsorted position.</mark>

Key points.

  1. Pass $i$ (for $i=0$ to $n-2$) scans $a[i..n-1]$ for the minimum and swaps it into $a[i]$.
  2. The scans need $(n-1)+\dots+1 = n(n-1)/2$ comparisons, so it is $O(n^2)$ in all cases.
  3. It makes at most $n-1$ swaps; it is in place but not stable.
  4. Algorithm: for i=0..n-2: min=i; for j=i+1..n-1: if a[j]<a[min] then min=j; swap(a[i],a[min]).

Asked: [7 marks] (Dec 2024) Explain how to sort the elements by using selection sort and derive time complexity for the same.

Heap sort

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Medium weight</span>

Definition. <mark>Heap sort builds a max-heap, a complete binary tree where every parent is $\ge$ its children, and then repeatedly swaps the root with the last element and re-heapifies the reduced heap.</mark>

Diagram. Initial tree (array order) and max-heap.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u5-02" viewBox="0 0 624 262" width="624" height="262" role="img" aria-label="Initial tree, numbers"><style>#dsfig-u5-02 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u5-02 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u5-02 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u5-02 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u5-02 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u5-02 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u5-02 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u5-02 .t{fill:#16181D;font-weight:500}#dsfig-u5-02 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u5-02 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u5-02 .dot{fill:#16181D}#dsfig-u5-02 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u5-02 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u5-02 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u5-02 .ah{fill:#454C5A}#dsfig-u5-02 .ah.hi{fill:#2340B8}#dsfig-u5-02 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u5-02 .wl .t{font-size:12px;font-weight:700}#dsfig-u5-02 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u5-02 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u5-02 .e{stroke:#B1B7C3}html.dark #dsfig-u5-02 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u5-02 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u5-02 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u5-02 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u5-02 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u5-02 .t{fill:#E6E8ED}html.dark #dsfig-u5-02 .t.inv{fill:#0F1115}html.dark #dsfig-u5-02 .kd{stroke:#E6E8ED}html.dark #dsfig-u5-02 .dot{fill:#E6E8ED}html.dark #dsfig-u5-02 .ann{fill:#8FA3FF}html.dark #dsfig-u5-02 .lbl{fill:#858D9C}html.dark #dsfig-u5-02 .ptr{fill:#8FA3FF}html.dark #dsfig-u5-02 .ah{fill:#B1B7C3}html.dark #dsfig-u5-02 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u5-02 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u5-02 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u5-02 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah51" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh51" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="344" y1="39" x2="168" y2="103"/><line class="e" x1="344" y1="39" x2="520" y2="103"/><line class="e" x1="168" y1="103" x2="80" y2="167"/><line class="e" x1="168" y1="103" x2="256" y2="167"/><line class="e" x1="80" y1="167" x2="36" y2="231"/><line class="e" x1="80" y1="167" x2="124" y2="231"/><line class="e" x1="256" y1="167" x2="212" y2="231"/><line class="e" x1="256" y1="167" x2="300" y2="231"/><line class="e" x1="520" y1="103" x2="432" y2="167"/><line class="e" x1="520" y1="103" x2="564" y2="167"/><line class="e" x1="432" y1="167" x2="388" y2="231"/><line class="e" x1="432" y1="167" x2="476" y2="231"/><circle class="n" cx="344" cy="39" r="17"/><text class="t" x="344" y="39" dy=".35em" text-anchor="middle">12</text><circle class="n" cx="168" cy="103" r="17"/><text class="t" x="168" y="103" dy=".35em" text-anchor="middle">8</text><circle class="n" cx="80" cy="167" r="17"/><text class="t" x="80" y="167" dy=".35em" text-anchor="middle">6</text><circle class="n" cx="36" cy="231" r="17"/><text class="t" x="36" y="231" dy=".35em" text-anchor="middle">11</text><circle class="n" cx="124" cy="231" r="17"/><text class="t" x="124" y="231" dy=".35em" text-anchor="middle">9</text><circle class="n" cx="256" cy="167" r="17"/><text class="t" x="256" y="167" dy=".35em" text-anchor="middle">4</text><circle class="n" cx="212" cy="231" r="17"/><text class="t" x="212" y="231" dy=".35em" text-anchor="middle">8</text><circle class="n" cx="300" cy="231" r="17"/><text class="t" x="300" y="231" dy=".35em" text-anchor="middle">14</text><circle class="n" cx="520" cy="103" r="17"/><text class="t" x="520" y="103" dy=".35em" text-anchor="middle">10</text><circle class="n" cx="432" cy="167" r="17"/><text class="t" x="432" y="167" dy=".35em" text-anchor="middle">10</text><circle class="n" cx="388" cy="231" r="17"/><text class="t" x="388" y="231" dy=".35em" text-anchor="middle">1</text><circle class="n" cx="476" cy="231" r="17"/><text class="t" x="476" y="231" dy=".35em" text-anchor="middle">2</text><circle class="n" cx="564" cy="167" r="17"/><text class="t" x="564" y="167" dy=".35em" text-anchor="middle">6</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Initial tree, numbers</figcaption></figure>

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u5-03" viewBox="0 0 624 262" width="624" height="262" role="img" aria-label="Max-heap after build-heap, numbers"><style>#dsfig-u5-03 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u5-03 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u5-03 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u5-03 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u5-03 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u5-03 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u5-03 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u5-03 .t{fill:#16181D;font-weight:500}#dsfig-u5-03 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u5-03 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u5-03 .dot{fill:#16181D}#dsfig-u5-03 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u5-03 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u5-03 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u5-03 .ah{fill:#454C5A}#dsfig-u5-03 .ah.hi{fill:#2340B8}#dsfig-u5-03 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u5-03 .wl .t{font-size:12px;font-weight:700}#dsfig-u5-03 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u5-03 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u5-03 .e{stroke:#B1B7C3}html.dark #dsfig-u5-03 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u5-03 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u5-03 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u5-03 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u5-03 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u5-03 .t{fill:#E6E8ED}html.dark #dsfig-u5-03 .t.inv{fill:#0F1115}html.dark #dsfig-u5-03 .kd{stroke:#E6E8ED}html.dark #dsfig-u5-03 .dot{fill:#E6E8ED}html.dark #dsfig-u5-03 .ann{fill:#8FA3FF}html.dark #dsfig-u5-03 .lbl{fill:#858D9C}html.dark #dsfig-u5-03 .ptr{fill:#8FA3FF}html.dark #dsfig-u5-03 .ah{fill:#B1B7C3}html.dark #dsfig-u5-03 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u5-03 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u5-03 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u5-03 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah52" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh52" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="344" y1="39" x2="168" y2="103"/><line class="e" x1="344" y1="39" x2="520" y2="103"/><line class="e" x1="168" y1="103" x2="80" y2="167"/><line class="e" x1="168" y1="103" x2="256" y2="167"/><line class="e" x1="80" y1="167" x2="36" y2="231"/><line class="e" x1="80" y1="167" x2="124" y2="231"/><line class="e" x1="256" y1="167" x2="212" y2="231"/><line class="e" x1="256" y1="167" x2="300" y2="231"/><line class="e" x1="520" y1="103" x2="432" y2="167"/><line class="e" x1="520" y1="103" x2="564" y2="167"/><line class="e" x1="432" y1="167" x2="388" y2="231"/><line class="e" x1="432" y1="167" x2="476" y2="231"/><circle class="n" cx="344" cy="39" r="17"/><text class="t" x="344" y="39" dy=".35em" text-anchor="middle">14</text><circle class="n" cx="168" cy="103" r="17"/><text class="t" x="168" y="103" dy=".35em" text-anchor="middle">12</text><circle class="n" cx="80" cy="167" r="17"/><text class="t" x="80" y="167" dy=".35em" text-anchor="middle">11</text><circle class="n" cx="36" cy="231" r="17"/><text class="t" x="36" y="231" dy=".35em" text-anchor="middle">6</text><circle class="n" cx="124" cy="231" r="17"/><text class="t" x="124" y="231" dy=".35em" text-anchor="middle">9</text><circle class="n" cx="256" cy="167" r="17"/><text class="t" x="256" y="167" dy=".35em" text-anchor="middle">8</text><circle class="n" cx="212" cy="231" r="17"/><text class="t" x="212" y="231" dy=".35em" text-anchor="middle">8</text><circle class="n" cx="300" cy="231" r="17"/><text class="t" x="300" y="231" dy=".35em" text-anchor="middle">4</text><circle class="n" cx="520" cy="103" r="17"/><text class="t" x="520" y="103" dy=".35em" text-anchor="middle">10</text><circle class="n" cx="432" cy="167" r="17"/><text class="t" x="432" y="167" dy=".35em" text-anchor="middle">10</text><circle class="n" cx="388" cy="231" r="17"/><text class="t" x="388" y="231" dy=".35em" text-anchor="middle">1</text><circle class="n" cx="476" cy="231" r="17"/><text class="t" x="476" y="231" dy=".35em" text-anchor="middle">2</text><circle class="n" cx="564" cy="167" r="17"/><text class="t" x="564" y="167" dy=".35em" text-anchor="middle">6</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Max-heap after build-heap, numbers</figcaption></figure>

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u5-04" viewBox="0 0 668 262" width="668" height="262" role="img" aria-label="Initial tree, letters"><style>#dsfig-u5-04 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u5-04 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u5-04 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u5-04 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u5-04 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u5-04 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u5-04 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u5-04 .t{fill:#16181D;font-weight:500}#dsfig-u5-04 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u5-04 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u5-04 .dot{fill:#16181D}#dsfig-u5-04 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u5-04 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u5-04 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u5-04 .ah{fill:#454C5A}#dsfig-u5-04 .ah.hi{fill:#2340B8}#dsfig-u5-04 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u5-04 .wl .t{font-size:12px;font-weight:700}#dsfig-u5-04 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u5-04 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u5-04 .e{stroke:#B1B7C3}html.dark #dsfig-u5-04 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u5-04 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u5-04 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u5-04 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u5-04 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u5-04 .t{fill:#E6E8ED}html.dark #dsfig-u5-04 .t.inv{fill:#0F1115}html.dark #dsfig-u5-04 .kd{stroke:#E6E8ED}html.dark #dsfig-u5-04 .dot{fill:#E6E8ED}html.dark #dsfig-u5-04 .ann{fill:#8FA3FF}html.dark #dsfig-u5-04 .lbl{fill:#858D9C}html.dark #dsfig-u5-04 .ptr{fill:#8FA3FF}html.dark #dsfig-u5-04 .ah{fill:#B1B7C3}html.dark #dsfig-u5-04 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u5-04 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u5-04 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u5-04 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah53" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh53" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="344" y1="39" x2="168" y2="103"/><line class="e" x1="344" y1="39" x2="520" y2="103"/><line class="e" x1="168" y1="103" x2="80" y2="167"/><line class="e" x1="168" y1="103" x2="256" y2="167"/><line class="e" x1="80" y1="167" x2="36" y2="231"/><line class="e" x1="80" y1="167" x2="124" y2="231"/><line class="e" x1="256" y1="167" x2="212" y2="231"/><line class="e" x1="256" y1="167" x2="300" y2="231"/><line class="e" x1="520" y1="103" x2="432" y2="167"/><line class="e" x1="520" y1="103" x2="608" y2="167"/><line class="e" x1="432" y1="167" x2="388" y2="231"/><line class="e" x1="432" y1="167" x2="476" y2="231"/><line class="e" x1="608" y1="167" x2="564" y2="231"/><circle class="n" cx="344" cy="39" r="17"/><text class="t" x="344" y="39" dy=".35em" text-anchor="middle">D</text><circle class="n" cx="168" cy="103" r="17"/><text class="t" x="168" y="103" dy=".35em" text-anchor="middle">A</text><circle class="n" cx="80" cy="167" r="17"/><text class="t" x="80" y="167" dy=".35em" text-anchor="middle">A</text><circle class="n" cx="36" cy="231" r="17"/><text class="t" x="36" y="231" dy=".35em" text-anchor="middle">U</text><circle class="n" cx="124" cy="231" r="17"/><text class="t" x="124" y="231" dy=".35em" text-anchor="middle">C</text><circle class="n" cx="256" cy="167" r="17"/><text class="t" x="256" y="167" dy=".35em" text-anchor="middle">S</text><circle class="n" cx="212" cy="231" r="17"/><text class="t" x="212" y="231" dy=".35em" text-anchor="middle">T</text><circle class="n" cx="300" cy="231" r="17"/><text class="t" x="300" y="231" dy=".35em" text-anchor="middle">U</text><circle class="n" cx="520" cy="103" r="17"/><text class="t" x="520" y="103" dy=".35em" text-anchor="middle">T</text><circle class="n" cx="432" cy="167" r="17"/><text class="t" x="432" y="167" dy=".35em" text-anchor="middle">T</text><circle class="n" cx="388" cy="231" r="17"/><text class="t" x="388" y="231" dy=".35em" text-anchor="middle">R</text><circle class="n" cx="476" cy="231" r="17"/><text class="t" x="476" y="231" dy=".35em" text-anchor="middle">E</text><circle class="n" cx="608" cy="167" r="17"/><text class="t" x="608" y="167" dy=".35em" text-anchor="middle">R</text><circle class="n" cx="564" cy="231" r="17"/><text class="t" x="564" y="231" dy=".35em" text-anchor="middle">S</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Initial tree, letters</figcaption></figure>

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u5-05" viewBox="0 0 668 262" width="668" height="262" role="img" aria-label="Max-heap after build-heap, letters"><style>#dsfig-u5-05 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u5-05 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u5-05 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u5-05 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u5-05 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u5-05 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u5-05 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u5-05 .t{fill:#16181D;font-weight:500}#dsfig-u5-05 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u5-05 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u5-05 .dot{fill:#16181D}#dsfig-u5-05 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u5-05 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u5-05 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u5-05 .ah{fill:#454C5A}#dsfig-u5-05 .ah.hi{fill:#2340B8}#dsfig-u5-05 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u5-05 .wl .t{font-size:12px;font-weight:700}#dsfig-u5-05 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u5-05 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u5-05 .e{stroke:#B1B7C3}html.dark #dsfig-u5-05 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u5-05 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u5-05 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u5-05 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u5-05 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u5-05 .t{fill:#E6E8ED}html.dark #dsfig-u5-05 .t.inv{fill:#0F1115}html.dark #dsfig-u5-05 .kd{stroke:#E6E8ED}html.dark #dsfig-u5-05 .dot{fill:#E6E8ED}html.dark #dsfig-u5-05 .ann{fill:#8FA3FF}html.dark #dsfig-u5-05 .lbl{fill:#858D9C}html.dark #dsfig-u5-05 .ptr{fill:#8FA3FF}html.dark #dsfig-u5-05 .ah{fill:#B1B7C3}html.dark #dsfig-u5-05 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u5-05 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u5-05 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u5-05 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah54" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh54" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="344" y1="39" x2="168" y2="103"/><line class="e" x1="344" y1="39" x2="520" y2="103"/><line class="e" x1="168" y1="103" x2="80" y2="167"/><line class="e" x1="168" y1="103" x2="256" y2="167"/><line class="e" x1="80" y1="167" x2="36" y2="231"/><line class="e" x1="80" y1="167" x2="124" y2="231"/><line class="e" x1="256" y1="167" x2="212" y2="231"/><line class="e" x1="256" y1="167" x2="300" y2="231"/><line class="e" x1="520" y1="103" x2="432" y2="167"/><line class="e" x1="520" y1="103" x2="608" y2="167"/><line class="e" x1="432" y1="167" x2="388" y2="231"/><line class="e" x1="432" y1="167" x2="476" y2="231"/><line class="e" x1="608" y1="167" x2="564" y2="231"/><circle class="n" cx="344" cy="39" r="17"/><text class="t" x="344" y="39" dy=".35em" text-anchor="middle">U</text><circle class="n" cx="168" cy="103" r="17"/><text class="t" x="168" y="103" dy=".35em" text-anchor="middle">U</text><circle class="n" cx="80" cy="167" r="17"/><text class="t" x="80" y="167" dy=".35em" text-anchor="middle">C</text><circle class="n" cx="36" cy="231" r="17"/><text class="t" x="36" y="231" dy=".35em" text-anchor="middle">A</text><circle class="n" cx="124" cy="231" r="17"/><text class="t" x="124" y="231" dy=".35em" text-anchor="middle">A</text><circle class="n" cx="256" cy="167" r="17"/><text class="t" x="256" y="167" dy=".35em" text-anchor="middle">T</text><circle class="n" cx="212" cy="231" r="17"/><text class="t" x="212" y="231" dy=".35em" text-anchor="middle">D</text><circle class="n" cx="300" cy="231" r="17"/><text class="t" x="300" y="231" dy=".35em" text-anchor="middle">S</text><circle class="n" cx="520" cy="103" r="17"/><text class="t" x="520" y="103" dy=".35em" text-anchor="middle">T</text><circle class="n" cx="432" cy="167" r="17"/><text class="t" x="432" y="167" dy=".35em" text-anchor="middle">T</text><circle class="n" cx="388" cy="231" r="17"/><text class="t" x="388" y="231" dy=".35em" text-anchor="middle">R</text><circle class="n" cx="476" cy="231" r="17"/><text class="t" x="476" y="231" dy=".35em" text-anchor="middle">E</text><circle class="n" cx="608" cy="167" r="17"/><text class="t" x="608" y="167" dy=".35em" text-anchor="middle">S</text><circle class="n" cx="564" cy="231" r="17"/><text class="t" x="564" y="231" dy=".35em" text-anchor="middle">R</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Max-heap after build-heap, letters</figcaption></figure>

Key points.

  1. Node $i$ has children $2i+1$ and $2i+2$ (0-based), so the tree is stored in the array.
  2. Heapify($i$) swaps a node with its larger child until the heap property holds.
  3. Build-heap calls heapify for $i=\lfloor n/2\rfloor-1$ down to $0$, costing $O(n)$.
  4. Each extraction swaps the root with the last heap element, shrinks the heap and heapifies the root in $O(\log n)$.
  5. Time is $O(n \log n)$ in all cases with $O(1)$ extra space, but it is not stable.
Step 1: Heapify(a,n,i): largest=i, l=2i+1, r=2i+2.
Step 2: if l<n and a[l]>a[largest] then largest=l; likewise for r.
Step 3: if largest!=i: swap a[i], a[largest]; Heapify(a,n,largest).
Step 4: HeapSort: for i=n/2-1 down to 0, Heapify(a,n,i).
Step 5: for end=n-1 down to 1: swap a[0], a[end]; Heapify(a,end,0).

Example. Build-heap for 12,8,10,6,4,10,6,11,9,8,14,1,2 ($n=13$, $i=5$ to 0):

$i$ (node) Swap Array after
5 (10) none, children 1, 2 unchanged
4 (4) 4 and 14 12,8,10,6,14,10,6,11,9,8,4,1,2
3 (6) 6 and 11 12,8,10,11,14,10,6,6,9,8,4,1,2
2 (10) none, children 10, 6 unchanged
1 (8) 8 and 14; 8 stays above 8, 4 12,14,10,11,8,10,6,6,9,8,4,1,2
0 (12) 12 and 14; 12 stays above 11, 8 14,12,10,11,8,10,6,6,9,8,4,1,2

Array after each root swap and heapify (heap|sorted tail).

12,11,10,9,8,10,6,6,2,8,4,1|14
11,9,10,6,8,10,6,1,2,8,4|12,14
10,9,10,6,8,4,6,1,2,8|11,12,14
10,9,8,6,8,4,6,1,2|10,11,12,14
9,8,8,6,2,4,6,1|10,10,11,12,14
8,6,8,1,2,4,6|9,10,10,11,12,14
8,6,6,1,2,4|8,9,10,10,11,12,14
6,4,6,1,2|8,8,9,10,10,11,12,14
6,4,2,1|6,8,8,9,10,10,11,12,14
4,1,2|6,6,8,8,9,10,10,11,12,14
2,1|4,6,6,8,8,9,10,10,11,12,14
1|2,4,6,6,8,8,9,10,10,11,12,14

Sorted: 1,2,4,6,6,8,8,9,10,10,11,12,14.

Letters ($n=14$, $i=6$ to 0): $i=6$ swaps R,S; $i=5$ none; $i=4$ S,U; $i=3$ A,U; $i=2$ none; $i=1$ A,U then A,C; $i=0$ sifts D down past U, U, T. Max-heap U,U,T,C,T,T,S,A,A,D,S,R,E,R, then 13 passes:

U,T,T,C,S,T,S,A,A,D,R,R,E|U
T,S,T,C,R,T,S,A,A,D,E,R|U,U
T,S,T,C,R,R,S,A,A,D,E|T,U,U
T,S,S,C,R,R,E,A,A,D|T,T,U,U
S,R,S,C,D,R,E,A,A|T,T,T,U,U
S,R,R,C,D,A,E,A|S,T,T,T,U,U
R,D,R,C,A,A,E|S,S,T,T,T,U,U
R,D,E,C,A,A|R,S,S,T,T,T,U,U
E,D,A,C,A|R,R,S,S,T,T,T,U,U
D,C,A,A|E,R,R,S,S,T,T,T,U,U
C,A,A|D,E,R,R,S,S,T,T,T,U,U
A,A|C,D,E,R,R,S,S,T,T,T,U,U
A|A,C,D,E,R,R,S,S,T,T,T,U,U

Sorted: A,A,C,D,E,R,R,S,S,T,T,T,U,U.

Answer frame. Open with the max-heap definition; write the algorithm; draw both trees; list the passes; close with $O(n \log n)$.

Asked: [7 marks] (Jun 2023, Dec 2023) Write the algorithm to create a heap and sort using heap sort: 12, 8, 10, 6, 4, 10, 6, 11, 9, 8, 14, 1, 2. Also write the heap sort algorithm and sort D A T A S T R U C T U R E S. Asked: [7 marks] (Nov 2022) Explain heap and radix sort with the algorithm.

Insertion sort

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>

Definition. <mark>Insertion sort inserts each element in turn into its correct place in the sorted part on its left.</mark>

Key points.

  1. Each pass takes the first unsorted element as key and shifts larger sorted elements one place right to make room.
  2. Best case is $O(n)$ for sorted input; the worst (reverse order) makes $n(n-1)/2$ comparisons and the average about $n^2/4$, so both are $O(n^2)$.
  3. It is stable, in place, and suits small or nearly sorted data.
Step 1: for i=1 to n-1: key=a[i], j=i-1.
Step 2: while j>=0 and a[j]>key: a[j+1]=a[j], j=j-1.
Step 3: a[j+1]=key.

Asked: [7 marks] (Dec 2022) Write the algorithm of insertion sort and find its time complexity.

Shell sort

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. <mark>Shell sort is a generalised insertion sort that first sorts elements a gap apart and then reduces the gap until it becomes 1.</mark>

Key points.

  1. A typical gap sequence starts at $n/2$ and halves each round, ending with insertion sort at gap 1.
  2. Distant elements move far at once, so the last pass is cheap; worst time is $O(n^2)$, in place, not stable.

Merge sort

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. <mark>Merge sort is a divide-and-conquer algorithm that splits the array into two halves, sorts each recursively and merges the two sorted halves into one sorted array.</mark>

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u5-06" viewBox="0 0 808 198" width="808" height="198" role="img" aria-label="Divide phase; merging back gives 27,38 and 3,43, then 3,27,38,43"><style>#dsfig-u5-06 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u5-06 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u5-06 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u5-06 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u5-06 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u5-06 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u5-06 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u5-06 .t{fill:#16181D;font-weight:500}#dsfig-u5-06 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u5-06 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u5-06 .dot{fill:#16181D}#dsfig-u5-06 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u5-06 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u5-06 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u5-06 .ah{fill:#454C5A}#dsfig-u5-06 .ah.hi{fill:#2340B8}#dsfig-u5-06 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u5-06 .wl .t{font-size:12px;font-weight:700}#dsfig-u5-06 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u5-06 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u5-06 .e{stroke:#B1B7C3}html.dark #dsfig-u5-06 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u5-06 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u5-06 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u5-06 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u5-06 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u5-06 .t{fill:#E6E8ED}html.dark #dsfig-u5-06 .t.inv{fill:#0F1115}html.dark #dsfig-u5-06 .kd{stroke:#E6E8ED}html.dark #dsfig-u5-06 .dot{fill:#E6E8ED}html.dark #dsfig-u5-06 .ann{fill:#8FA3FF}html.dark #dsfig-u5-06 .lbl{fill:#858D9C}html.dark #dsfig-u5-06 .ptr{fill:#8FA3FF}html.dark #dsfig-u5-06 .ah{fill:#B1B7C3}html.dark #dsfig-u5-06 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u5-06 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u5-06 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u5-06 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah55" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh55" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="392" y1="39" x2="176" y2="103"/><line class="e" x1="392" y1="39" x2="608" y2="103"/><line class="e" x1="176" y1="103" x2="68" y2="167"/><line class="e" x1="176" y1="103" x2="284" y2="167"/><line class="e" x1="608" y1="103" x2="500" y2="167"/><line class="e" x1="608" y1="103" x2="716" y2="167"/><rect class="n" x="343" y="24" width="98" height="30" rx="8"/><text class="t" x="392" y="39" dy=".35em" text-anchor="middle">38 27 43 3</text><rect class="n" x="146.5" y="88" width="59" height="30" rx="8"/><text class="t" x="176" y="103" dy=".35em" text-anchor="middle">38 27</text><circle class="n" cx="68" cy="167" r="17"/><text class="t" x="68" y="167" dy=".35em" text-anchor="middle">38</text><circle class="n" cx="284" cy="167" r="17"/><text class="t" x="284" y="167" dy=".35em" text-anchor="middle">27</text><rect class="n" x="582" y="88" width="52" height="30" rx="8"/><text class="t" x="608" y="103" dy=".35em" text-anchor="middle">43 3</text><circle class="n" cx="500" cy="167" r="17"/><text class="t" x="500" y="167" dy=".35em" text-anchor="middle">43</text><circle class="n" cx="716" cy="167" r="17"/><text class="t" x="716" y="167" dy=".35em" text-anchor="middle">3</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Divide phase; merging back gives 27,38 and 3,43, then 3,27,38,43</figcaption></figure>

Key points.

  1. Divide splits the array at the middle until each part has one element; conquer sorts both halves recursively.
  2. Combine merges by comparing the fronts of the two sorted halves and copying the smaller into a temporary array.
  3. There are $\log_2 n$ levels each costing $O(n)$ to merge, so $T(n)=2T(n/2)+n$ gives $O(n \log n)$ in all cases.
  4. It needs $O(n)$ extra space, so it is not in place, but it is stable, and it underlies external sorting.
Step 1: MergeSort(a,lo,hi): if lo<hi: mid=(lo+hi)/2.
Step 2:   MergeSort(a,lo,mid); MergeSort(a,mid+1,hi); Merge(a,lo,mid,hi).
Step 3: Merge: i=lo, j=mid+1, k=lo.
Step 4: while i<=mid and j<=hi: if a[i]<=a[j] then b[k++]=a[i++] else b[k++]=a[j++].
Step 5: copy the rest of a[i..mid] or a[j..hi] to b; copy b[lo..hi] back to a.

Answer frame. Open with the definition; draw the split tree; explain divide, conquer, combine; close with the complexity.

Short note: Graph. A graph $G=(V,E)$ is a set of vertices $V$ joined by a set of edges $E$.

  1. An undirected edge $(u,v)$ runs both ways, a directed edge $\langle u,v\rangle$ one way, and a weighted edge carries a cost.
  2. An adjacency matrix is a $V \times V$ array with $a[i][j]=1$ (or the weight) for an edge: $O(V^2)$ space.
  3. An adjacency list keeps neighbours per vertex: $O(V+E)$ space, best for sparse graphs.
  4. Degree is the number of edges at a vertex; in a digraph, in-degree counts incoming and out-degree outgoing edges.
  5. A path is a vertex sequence joined by edges, a cycle is a path ending where it starts, and a connected graph has a path between every pair.
  6. Traversal uses BFS (level by level, queue) or DFS (deepest first, stack).

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u5-07" viewBox="0 0 338 252" width="338" height="252" role="img" aria-label="Weighted undirected graph; adjacency list A-B,C; B-A,D; C-A,D; D-B,C"><style>#dsfig-u5-07 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u5-07 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u5-07 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u5-07 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u5-07 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u5-07 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u5-07 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u5-07 .t{fill:#16181D;font-weight:500}#dsfig-u5-07 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u5-07 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u5-07 .dot{fill:#16181D}#dsfig-u5-07 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u5-07 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u5-07 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u5-07 .ah{fill:#454C5A}#dsfig-u5-07 .ah.hi{fill:#2340B8}#dsfig-u5-07 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u5-07 .wl .t{font-size:12px;font-weight:700}#dsfig-u5-07 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u5-07 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u5-07 .e{stroke:#B1B7C3}html.dark #dsfig-u5-07 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u5-07 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u5-07 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u5-07 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u5-07 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u5-07 .t{fill:#E6E8ED}html.dark #dsfig-u5-07 .t.inv{fill:#0F1115}html.dark #dsfig-u5-07 .kd{stroke:#E6E8ED}html.dark #dsfig-u5-07 .dot{fill:#E6E8ED}html.dark #dsfig-u5-07 .ann{fill:#8FA3FF}html.dark #dsfig-u5-07 .lbl{fill:#858D9C}html.dark #dsfig-u5-07 .ptr{fill:#8FA3FF}html.dark #dsfig-u5-07 .ah{fill:#B1B7C3}html.dark #dsfig-u5-07 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u5-07 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u5-07 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u5-07 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah56" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh56" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M55.8,115.5 L153.2,50.5"/><path class="e" d="M55.8,136.5 L153.2,201.5"/><path class="e" d="M184.8,50.5 L282.2,115.5"/><path class="e" d="M184.8,201.5 L282.2,136.5"/><g class="wl"><rect x="94.9" y="74" width="19.2" height="18" rx="9"/><text class="t" x="104.5" y="83" dy=".35em" text-anchor="middle">4</text></g><g class="wl"><rect x="94.9" y="160" width="19.2" height="18" rx="9"/><text class="t" x="104.5" y="169" dy=".35em" text-anchor="middle">2</text></g><g class="wl"><rect x="223.9" y="74" width="19.2" height="18" rx="9"/><text class="t" x="233.5" y="83" dy=".35em" text-anchor="middle">5</text></g><g class="wl"><rect x="223.9" y="160" width="19.2" height="18" rx="9"/><text class="t" x="233.5" y="169" dy=".35em" text-anchor="middle">1</text></g><circle class="n" cx="40" cy="126" r="18"/><text class="t" x="40" y="126" dy=".35em" text-anchor="middle">A</text><circle class="n" cx="169" cy="40" r="18"/><text class="t" x="169" y="40" dy=".35em" text-anchor="middle">B</text><circle class="n" cx="169" cy="212" r="18"/><text class="t" x="169" y="212" dy=".35em" text-anchor="middle">C</text><circle class="n" cx="298" cy="126" r="18"/><text class="t" x="298" y="126" dy=".35em" text-anchor="middle">D</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Weighted undirected graph; adjacency list A-B,C; B-A,D; C-A,D; D-B,C</figcaption></figure>

A B C D
A 0 4 2 0
B 4 0 0 5
C 2 0 0 1
D 0 5 1 0

Short note: B+ tree. A B+ tree of order $m$ is a balanced multiway search tree whose internal nodes hold only index keys and whose leaves hold every key with its record.

  1. A node has at most $m$ children and $m-1$ keys, non-root nodes are half full, and all leaves lie on one level.
  2. Internal keys are copies that only guide the search, and linked leaves let a range query walk the chain.
  3. Unlike a B-tree, which stores each key once with its data in any node, a B+ tree keeps data only in leaves, so DBMS indexes use it.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u5-08" viewBox="0 0 188 134" width="188" height="134" role="img" aria-label="B+ tree of order 3; 30 repeats in a leaf, and the leaves are linked"><style>#dsfig-u5-08 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u5-08 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u5-08 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u5-08 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u5-08 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u5-08 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u5-08 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u5-08 .t{fill:#16181D;font-weight:500}#dsfig-u5-08 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u5-08 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u5-08 .dot{fill:#16181D}#dsfig-u5-08 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u5-08 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u5-08 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u5-08 .ah{fill:#454C5A}#dsfig-u5-08 .ah.hi{fill:#2340B8}#dsfig-u5-08 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u5-08 .wl .t{font-size:12px;font-weight:700}#dsfig-u5-08 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u5-08 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u5-08 .e{stroke:#B1B7C3}html.dark #dsfig-u5-08 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u5-08 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u5-08 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u5-08 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u5-08 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u5-08 .t{fill:#E6E8ED}html.dark #dsfig-u5-08 .t.inv{fill:#0F1115}html.dark #dsfig-u5-08 .kd{stroke:#E6E8ED}html.dark #dsfig-u5-08 .dot{fill:#E6E8ED}html.dark #dsfig-u5-08 .ann{fill:#8FA3FF}html.dark #dsfig-u5-08 .lbl{fill:#858D9C}html.dark #dsfig-u5-08 .ptr{fill:#8FA3FF}html.dark #dsfig-u5-08 .ah{fill:#B1B7C3}html.dark #dsfig-u5-08 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u5-08 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u5-08 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u5-08 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah57" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh57" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="82" y1="39" x2="44" y2="103"/><line class="e" x1="82" y1="39" x2="120" y2="103"/><circle class="n" cx="82" cy="39" r="17"/><text class="t" x="82" y="39" dy=".35em" text-anchor="middle">30</text><rect class="n" x="14" y="88" width="60" height="30" rx="3"/><text class="t" x="29" y="103" dy=".35em" text-anchor="middle">10</text><line class="kd" x1="44" y1="88" x2="44" y2="118"/><text class="t" x="59" y="103" dy=".35em" text-anchor="middle">20</text><rect class="n" x="90" y="88" width="60" height="30" rx="3"/><text class="t" x="105" y="103" dy=".35em" text-anchor="middle">30</text><line class="kd" x1="120" y1="88" x2="120" y2="118"/><text class="t" x="135" y="103" dy=".35em" text-anchor="middle">40</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">B+ tree of order 3; 30 repeats in a leaf, and the leaves are linked</figcaption></figure>

Insert 25: leaf 10|20|25 overflows (max 2 keys), splits into 10 and 20|25, and the middle key 20 is copied up into the parent.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u5-09" viewBox="0 0 238 134" width="238" height="134" role="img" aria-label="After inserting 25, leaf split, 20 copied up"><style>#dsfig-u5-09 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u5-09 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u5-09 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u5-09 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u5-09 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u5-09 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u5-09 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u5-09 .t{fill:#16181D;font-weight:500}#dsfig-u5-09 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u5-09 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u5-09 .dot{fill:#16181D}#dsfig-u5-09 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u5-09 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u5-09 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u5-09 .ah{fill:#454C5A}#dsfig-u5-09 .ah.hi{fill:#2340B8}#dsfig-u5-09 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u5-09 .wl .t{font-size:12px;font-weight:700}#dsfig-u5-09 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u5-09 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u5-09 .e{stroke:#B1B7C3}html.dark #dsfig-u5-09 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u5-09 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u5-09 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u5-09 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u5-09 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u5-09 .t{fill:#E6E8ED}html.dark #dsfig-u5-09 .t.inv{fill:#0F1115}html.dark #dsfig-u5-09 .kd{stroke:#E6E8ED}html.dark #dsfig-u5-09 .dot{fill:#E6E8ED}html.dark #dsfig-u5-09 .ann{fill:#8FA3FF}html.dark #dsfig-u5-09 .lbl{fill:#858D9C}html.dark #dsfig-u5-09 .ptr{fill:#8FA3FF}html.dark #dsfig-u5-09 .ah{fill:#B1B7C3}html.dark #dsfig-u5-09 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u5-09 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u5-09 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u5-09 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah58" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh58" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><line class="e" x1="70.5" y1="54" x2="31" y2="103"/><line class="e" x1="100.5" y1="54" x2="94" y2="103"/><line class="e" x1="130.5" y1="54" x2="170" y2="103"/><rect class="n" x="70.5" y="24" width="60" height="30" rx="3"/><text class="t" x="85.5" y="39" dy=".35em" text-anchor="middle">20</text><line class="kd" x1="100.5" y1="24" x2="100.5" y2="54"/><text class="t" x="115.5" y="39" dy=".35em" text-anchor="middle">30</text><circle class="n" cx="31" cy="103" r="17"/><text class="t" x="31" y="103" dy=".35em" text-anchor="middle">10</text><rect class="n" x="64" y="88" width="60" height="30" rx="3"/><text class="t" x="79" y="103" dy=".35em" text-anchor="middle">20</text><line class="kd" x1="94" y1="88" x2="94" y2="118"/><text class="t" x="109" y="103" dy=".35em" text-anchor="middle">25</text><rect class="n" x="140" y="88" width="60" height="30" rx="3"/><text class="t" x="155" y="103" dy=".35em" text-anchor="middle">30</text><line class="kd" x1="170" y1="88" x2="170" y2="118"/><text class="t" x="185" y="103" dy=".35em" text-anchor="middle">40</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">After inserting 25, leaf split, 20 copied up</figcaption></figure>

Short note: Deque. A deque (double-ended queue) is a linear list that allows insertion and deletion at both front and rear.

  1. insertFront, insertRear, deleteFront and deleteRear are each $O(1)$ in a circular array or doubly linked list, so a deque can act as a stack or a queue.
  2. An input-restricted deque inserts at one end only; an output-restricted deque deletes at one end only.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u5-10" viewBox="0 0 447 58" width="447" height="58" role="img" aria-label="Deque as a doubly linked list; front 10, rear 40"><style>#dsfig-u5-10 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u5-10 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u5-10 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u5-10 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u5-10 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u5-10 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u5-10 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u5-10 .t{fill:#16181D;font-weight:500}#dsfig-u5-10 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u5-10 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u5-10 .dot{fill:#16181D}#dsfig-u5-10 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u5-10 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u5-10 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u5-10 .ah{fill:#454C5A}#dsfig-u5-10 .ah.hi{fill:#2340B8}#dsfig-u5-10 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u5-10 .wl .t{font-size:12px;font-weight:700}#dsfig-u5-10 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u5-10 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u5-10 .e{stroke:#B1B7C3}html.dark #dsfig-u5-10 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u5-10 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u5-10 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u5-10 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u5-10 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u5-10 .t{fill:#E6E8ED}html.dark #dsfig-u5-10 .t.inv{fill:#0F1115}html.dark #dsfig-u5-10 .kd{stroke:#E6E8ED}html.dark #dsfig-u5-10 .dot{fill:#E6E8ED}html.dark #dsfig-u5-10 .ann{fill:#8FA3FF}html.dark #dsfig-u5-10 .lbl{fill:#858D9C}html.dark #dsfig-u5-10 .ptr{fill:#8FA3FF}html.dark #dsfig-u5-10 .ah{fill:#B1B7C3}html.dark #dsfig-u5-10 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u5-10 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u5-10 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u5-10 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah59" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh59" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><text class="ptr" x="14" y="29" dy=".35em" text-anchor="start">front</text><line class="e" x1="59" y1="29" x2="82" y2="29" marker-end="url(#ah59)"/><rect class="n" x="83" y="14" width="62" height="30" rx="3"/><line class="kd" x1="99" y1="14" x2="99" y2="44"/><text class="t" x="114" y="29" dy=".35em" text-anchor="middle">10</text><line class="kd" x1="129" y1="14" x2="129" y2="44"/><line class="kd" x1="86" y1="41" x2="96" y2="17"/><circle class="dot" cx="137" cy="23.6" r="2.6"/><line class="e" x1="137" y1="23.6" x2="178" y2="23.6" marker-end="url(#ah59)"/><circle class="dot" cx="187" cy="34.4" r="2.6"/><line class="e" x1="187" y1="34.4" x2="146" y2="34.4" marker-end="url(#ah59)"/><rect class="n" x="179" y="14" width="62" height="30" rx="3"/><line class="kd" x1="195" y1="14" x2="195" y2="44"/><text class="t" x="210" y="29" dy=".35em" text-anchor="middle">20</text><line class="kd" x1="225" y1="14" x2="225" y2="44"/><circle class="dot" cx="233" cy="23.6" r="2.6"/><line class="e" x1="233" y1="23.6" x2="274" y2="23.6" marker-end="url(#ah59)"/><circle class="dot" cx="283" cy="34.4" r="2.6"/><line class="e" x1="283" y1="34.4" x2="242" y2="34.4" marker-end="url(#ah59)"/><rect class="n" x="275" y="14" width="62" height="30" rx="3"/><line class="kd" x1="291" y1="14" x2="291" y2="44"/><text class="t" x="306" y="29" dy=".35em" text-anchor="middle">30</text><line class="kd" x1="321" y1="14" x2="321" y2="44"/><circle class="dot" cx="329" cy="23.6" r="2.6"/><line class="e" x1="329" y1="23.6" x2="370" y2="23.6" marker-end="url(#ah59)"/><circle class="dot" cx="379" cy="34.4" r="2.6"/><line class="e" x1="379" y1="34.4" x2="338" y2="34.4" marker-end="url(#ah59)"/><rect class="n" x="371" y="14" width="62" height="30" rx="3"/><line class="kd" x1="387" y1="14" x2="387" y2="44"/><text class="t" x="402" y="29" dy=".35em" text-anchor="middle">40</text><line class="kd" x1="417" y1="14" x2="417" y2="44"/><line class="kd" x1="420" y1="41" x2="430" y2="17"/></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Deque as a doubly linked list; front 10, rear 40</figcaption></figure>

Asked: [14 marks] (Dec 2024) Write short notes (any three): i) Merge Sort ii) Graph iii) B+ Tree iv) Dqueue.

Radix sort

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. <mark>Radix sort sorts numbers digit by digit, least significant first, using a stable counting sort for each digit.</mark>

Key points.

  1. Every pass is stable, so earlier digit order is kept and the last pass leaves the list sorted.
  2. For $n$ numbers of $d$ digits with base $k$, time is $O(d(n+k))$, with $O(n+k)$ extra space.
  3. It uses no comparisons, so it can beat $O(n \log n)$.

Example. 170,45,75,90,802,24,2,66. After units: 170,90,802,2,24,45,75,66; after tens: 802,2,24,45,66,170,75,90; after hundreds: 2,24,45,66,75,90,170,802.

Step 1: for exp=1, 10, 100, ... while max/exp>0, do Steps 2-4.
Step 2: count[d]=number of a[i] whose digit (a[i]/exp)%10 is d; prefix-sum count.
Step 3: for i=n-1 down to 0: d=digit of a[i]; count[d]--; out[count[d]]=a[i].
Step 4: copy out[] back to a[].

Comparison of various sorting techniques

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. <mark>A stable sort keeps equal keys in their original relative order, and an in-place sort needs only $O(1)$ (or very small) extra memory.</mark>

Key points.

  1. Stable: merge, insertion, bubble; unstable: quick, heap, selection.
  2. In place: bubble, selection, insertion, heap, quick; not in place: merge and radix.
Algorithm Best Average Worst Space Stable
Bubble $O(n)$ $O(n^2)$ $O(n^2)$ $O(1)$ Yes
Selection $O(n^2)$ $O(n^2)$ $O(n^2)$ $O(1)$ No
Insertion $O(n)$ $O(n^2)$ $O(n^2)$ $O(1)$ Yes
Quick $O(n \log n)$ $O(n \log n)$ $O(n^2)$ $O(\log n)$ No
Merge $O(n \log n)$ $O(n \log n)$ $O(n \log n)$ $O(n)$ Yes
Heap $O(n \log n)$ $O(n \log n)$ $O(n \log n)$ $O(1)$ No

Internal versus external sorting.

Basis Internal sorting External sorting
Storage Main memory (RAM), data fits Disk or tape, data exceeds memory
Speed Fast, no I/O Slow, disk I/O
Method Random access to whole array Sorted runs made, then merged
Cost measure Comparisons and swaps Disk passes
Examples Quick sort, bubble sort, heap sort Multiway merge sort, polyphase merge sort

Unstable example. Selection sort on 2a, 2b, 1 swaps 1 with 2a, giving 1, 2b, 2a: equal keys change order; a stable sort gives 1, 2a, 2b.

External merge. Memory-sized runs are sorted, then a k-way merge needs $\lceil\log_k r\rceil$ passes: 10 runs take 4 passes 2-way.

Answer frame. Internal versus external: definitions, table, merge note, two examples each. Stable and in-place: define both, list points 1-2.

Asked: [7 marks] (Dec 2022, Jun 2023) Difference between internal sorting and external sorting. Asked: [7 marks] (Jun 2023) Differentiate internal sorting and external sorting. Also list the names of two sorting techniques of each. Asked: [5 marks] (Dec 2023) What do you understand by stable and in-place sorting?

Sequential search

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Not asked since 2022</span>

Definition. <mark>Sequential (linear) search examines the elements one by one from the start until the key is found or the list ends.</mark>

Key points.

  1. It works on unsorted data and needs no extra structure.
  2. Best case is 1 comparison, the worst is $n$, and the average for a present key is $(n+1)/2$, so $O(n)$.
  3. Space is $O(1)$.

Binary search

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>

Definition. <mark>Binary search finds a key in a sorted array by repeatedly comparing it with the middle element and discarding the half that cannot contain it.</mark>

Key points.

  1. The array must be sorted; keep low, high and $mid=\lfloor (low+high)/2\rfloor$.
  2. If $a[mid]$ equals the key, stop; if the key is smaller set $high=mid-1$, else $low=mid+1$.
  3. The space halves each step, so $T(n)=T(n/2)+1$ gives $O(\log_2 n)$: best case $O(1)$ (key at the first mid), average and worst $O(\log n)$, space $O(1)$ if iterative. Example. 10,20,30,40,50,60,70,80,90, key 70: mid=4 (50<70) so low=5; mid=6 gives 70, found at index 6 in 2 comparisons. Key 35 ends with low>high, not found.

Answer frame. Open with the sorted-array prerequisite; write the steps and trace; close with $O(\log n)$.

Asked: [7 marks] (Dec 2025) Explain Binary Search with an example.

Comparison of search methods

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>

Definition. <mark>Linear search checks elements one by one in $O(n)$, while binary search halves a sorted list each step in $O(\log n)$.</mark>

Basis Linear search Binary search
Data Any order Must be sorted
Time (worst) $O(n)$ $O(\log n)$
Comparisons for $n=10^6$ up to $10^6$ about 20

Key points.

  1. Binary search is more efficient because each comparison removes half the remaining elements, linear search only one.
  2. It needs sorted data, so linear search suits one search of unsorted data.

Asked: [7 marks] (Jun 2023) Binary search is more efficient than Linear search. Justify your answer.

Hashing & Indexing

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. <mark>Hashing maps a key from a large key universe to an address in the small range $0..m-1$ of a hash table using a hash function $h(k)$, so that searching, insertion and deletion take $O(1)$ time on average.</mark> A hash table is an array of $m$ slots, each record stored at its key's hash. It generalises direct addressing, where the key itself is the index.

Key points.

  1. A good hash function is fast and spreads keys uniformly; a collision is $h(k_1)=h(k_2)$ for different keys.
  2. Division method: $h(k)=k \bmod m$ with $m$ a prime not near a power of 2; $1234 \bmod 11=2$.
  3. Mid-square: square the key and take the middle $r$ digits for a table of $10^r$ slots, e.g. $123^2=15129$ gives 512 for 1000 slots.
  4. Folding: split the key into equal parts and add them. Shift folding adds the parts as they are: 123+456+789 = 1368, or 368 without the carry; boundary folding reverses alternate parts: 123+654+789 = 1566, or 566.
  5. Multiplication method: $h(k)=\lfloor m\,(kA \bmod 1)\rfloor$ with $0<A<1$; for $k=123$, $A=0.618$, $m=100$: $kA=76.014$, fraction $0.014$, so $h=\lfloor 1.4\rfloor=1$.
  6. Separate chaining keeps a linked list of colliding keys at each slot.
  7. Open addressing stores keys in the table itself: linear probing tries $(h(k)+i)\bmod m$, quadratic probing $(h(k)+i^2)\bmod m$, and double hashing $(h_1(k)+i\,h_2(k))\bmod m$ for $i=0,1,2,\dots$
  8. Linear probing builds primary clustering (long filled runs); quadratic has secondary clustering (same home, same probes); double hashing avoids both.
  9. Load factor $\alpha=n/m$; past about 0.7, rehash into a table twice as large.

Example. $m=7$, $h(k)=k \bmod 7$, keys 50,700,76,85,92,73,101 (homes 1,0,6,1,1,3,3); double hashing uses $h_2(k)=5-(k \bmod 5)$.

Probe sequences, last slot free. Linear: 85: 1,2; 92: 1,2,3; 101: 3,4,5. Quadratic 92: 1,2,5. Double: 85 ($h_2=5$): 1,6,4; 92 ($h_2=3$): 1,4,0,3; 73 ($h_2=2$): 3,5; 101 ($h_2=4$): 3,0,4,1,5,2.

Method Slots 0-6 after all keys
Linear 700,50,85,92,73,101,76
Quadratic 700,50,85,73,101,92,76
Double 700,50,101,92,85,73,76
Basis Chaining
--- ---
Storage Lists outside the table
Load factor $\alpha$ may exceed 1
Clustering None
Deletion Easy
Memory Extra pointers

HashMap. A HashMap stores key-value pairs in buckets chosen by the key's hash; colliding keys are chained in one bucket and matched by key comparison (equals() in Java). Java starts with 16 buckets, load factor 0.75, and turns a chain of 8 into a red-black tree.

struct node { int key; int val; struct node *next; } *t[7];
void put(int k, int v){ struct node *n = malloc(sizeof *n);
  n->key = k; n->val = v; n->next = t[k % 7]; t[k % 7] = n; } /* 50, 85: slot 1 */
int get(int k){ struct node *p = t[k % 7];
  while (p && p->key != k) p = p->next;   /* walk the chain, compare keys */
  return p ? p->val : -1; }               /* get(85) after put(85,9): 9 */

Linear probing: put tries k%m, k%m+1, ... until a slot is free; get probes the same way until the key or an empty slot.

Indexing. An index maps keys to record locations: dense has an entry per record, sparse one per block; primary is on the ordering key, secondary on another field.

Dense index Sparse index
101→R1, 102→R2, 103→R3, 104→R4 101→Block 1 (101-102), 103→Block 2 (103-104)

Key 103 is found by searching the index to Block 2. Hashing gives $O(1)$ exact lookup but no range queries; an ordered index gives $O(\log n)$ and ranges.

Applications. Password storage keeps only a salted hash; a compiler symbol table hashes identifiers; a cache (web, DNS) hashes a request to its stored result, so a repeat is not recomputed; a database hash index hashes the key to the bucket holding the row address, so a lookup reads one bucket; a blockchain stores each block's hash in the next, so altering a block breaks every later hash; a checksum or digital signature hashes the data, and the receiver recomputes it to prove nothing changed.

Answer frame. Open with the definition; draw the chained table; develop hash functions, chaining, open addressing; close with average $O(1)$. Applications: list four, explain two.

Asked: [7 marks] (Dec 2022) What is Hashing? Explain different hash functions in detail. Asked: [7 marks] (Dec 2023) Define hash function. Discuss various methods used for resolving hash collisions. Asked: [7 marks] (Jun 2023) Write short note on Hashing and Indexing. Asked: [7 marks] (Dec 2024) Provide examples of real-world applications where hashing is used and explain any two examples in detail. Asked: [7 marks] (Jun 2024) What is HashMap in data structure? How does HashMap handle collisions? Explain with C or Java.

Case Study: Application of data structures in operating system, DBMS

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>

Definition. <mark>LRU (Least Recently Used) replaces the page or cache entry that has not been used for the longest time.</mark>

Key points.

  1. An LRU cache uses a doubly linked list (head most recent) plus a hash map from key to node, so get and put are $O(1)$; the OS uses it for page replacement, a DBMS for buffer pages.
  2. A hit moves the page to the head; a miss with full frames evicts the tail page.

Example. 3 frames, references 7,0,1,2,0,3,0,4 (frames listed MRU first).

Ref 7 0 1 2 0 3 0 4
Frames 7 0,7 1,0,7 2,1,0 0,2,1 3,0,2 0,3,2 4,0,3
Result F F F F, evict 7 Hit F, evict 1 Hit F, evict 2

6 faults, 2 hits, fault ratio 6/8 = 0.75.

<figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u5-11" viewBox="0 0 344 58" width="344" height="58" role="img" aria-label="Final list, head MRU 4, tail LRU 3; map keys 4, 0, 3"><style>#dsfig-u5-11 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u5-11 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u5-11 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u5-11 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u5-11 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u5-11 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u5-11 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u5-11 .t{fill:#16181D;font-weight:500}#dsfig-u5-11 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u5-11 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u5-11 .dot{fill:#16181D}#dsfig-u5-11 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u5-11 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u5-11 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u5-11 .ah{fill:#454C5A}#dsfig-u5-11 .ah.hi{fill:#2340B8}#dsfig-u5-11 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u5-11 .wl .t{font-size:12px;font-weight:700}#dsfig-u5-11 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u5-11 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u5-11 .e{stroke:#B1B7C3}html.dark #dsfig-u5-11 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u5-11 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u5-11 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u5-11 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u5-11 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u5-11 .t{fill:#E6E8ED}html.dark #dsfig-u5-11 .t.inv{fill:#0F1115}html.dark #dsfig-u5-11 .kd{stroke:#E6E8ED}html.dark #dsfig-u5-11 .dot{fill:#E6E8ED}html.dark #dsfig-u5-11 .ann{fill:#8FA3FF}html.dark #dsfig-u5-11 .lbl{fill:#858D9C}html.dark #dsfig-u5-11 .ptr{fill:#8FA3FF}html.dark #dsfig-u5-11 .ah{fill:#B1B7C3}html.dark #dsfig-u5-11 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u5-11 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u5-11 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u5-11 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah60" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh60" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><text class="ptr" x="14" y="29" dy=".35em" text-anchor="start">head</text><line class="e" x1="52" y1="29" x2="75" y2="29" marker-end="url(#ah60)"/><rect class="n hi" x="76" y="14" width="62" height="30" rx="3"/><line class="kd" x1="92" y1="14" x2="92" y2="44"/><text class="t" x="107" y="29" dy=".35em" text-anchor="middle">4</text><line class="kd" x1="122" y1="14" x2="122" y2="44"/><line class="kd" x1="79" y1="41" x2="89" y2="17"/><circle class="dot" cx="130" cy="23.6" r="2.6"/><line class="e" x1="130" y1="23.6" x2="171" y2="23.6" marker-end="url(#ah60)"/><circle class="dot" cx="180" cy="34.4" r="2.6"/><line class="e" x1="180" y1="34.4" x2="139" y2="34.4" marker-end="url(#ah60)"/><rect class="n" x="172" y="14" width="62" height="30" rx="3"/><line class="kd" x1="188" y1="14" x2="188" y2="44"/><text class="t" x="203" y="29" dy=".35em" text-anchor="middle">0</text><line class="kd" x1="218" y1="14" x2="218" y2="44"/><circle class="dot" cx="226" cy="23.6" r="2.6"/><line class="e" x1="226" y1="23.6" x2="267" y2="23.6" marker-end="url(#ah60)"/><circle class="dot" cx="276" cy="34.4" r="2.6"/><line class="e" x1="276" y1="34.4" x2="235" y2="34.4" marker-end="url(#ah60)"/><rect class="n" x="268" y="14" width="62" height="30" rx="3"/><line class="kd" x1="284" y1="14" x2="284" y2="44"/><text class="t" x="299" y="29" dy=".35em" text-anchor="middle">3</text><line class="kd" x1="314" y1="14" x2="314" y2="44"/><line class="kd" x1="317" y1="41" x2="327" y2="17"/></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Final list, head MRU 4, tail LRU 3; map keys 4, 0, 3</figcaption></figure>

Step 1: get(k): if k is not in the map, return -1 (miss).
Step 2: else move node map[k] to the head and return its value (hit).
Step 3: put(k,v): if k is in the map, update its value and move it to the head.
Step 4: else if the cache is full, remove the tail node and delete its key from the map.
Step 5: create a node (k,v), insert it at the head and set map[k]=node.

Asked: [7 marks] (Jun 2024) Demonstrate LRU Algorithm. Which data structure uses LRU algorithm.

Last-minute revision

  • Quick sort: $O(n \log n)$ average, $O(n^2)$ worst, unstable.
  • Heap sort: build-heap $O(n)$, sort $O(n \log n)$.
  • Binary search: sorted input, $O(\log n)$; $10^6$ elements need about 20 comparisons.
  • Hash: $\alpha=n/m$; external k-way merge: $\lceil\log_k r\rceil$ passes.

Memory hooks

  • Stable: "Bubble, Insertion, Merge" (BIM).
  • Chaining = outside; open addressing = inside.

Coverage checklist

  • Introduction: covered.
  • Sort methods like: Bubble Sort: covered.
  • Quick sort: Dec 2022, Dec 2025.
  • Selection sort: Dec 2024.
  • Heap sort: Nov 2022, Jun 2023, Dec 2023.
  • Insertion sort: Dec 2022.
  • Shell sort: covered.
  • Merge sort: Dec 2024.
  • Radix sort: covered (also Nov 2022 with heap sort).
  • comparison of various sorting techniques: Dec 2022, Jun 2023, Dec 2023.
  • Searching: Basic Search Techniques: Sequential search: covered.
  • Binary search: Dec 2025.
  • Comparison of search methods: Jun 2023.
  • Hashing & Indexing: Dec 2022, Jun 2023, Dec 2023, Jun 2024, Dec 2024.
  • Case Study: Application of various data structures in operating system, DBMS etc: Jun 2024.
Go to where you left off?

Quick Add to Notes

Save questions, your own notes and screenshots into notes filed by unit. It takes a free account.

Create free account

Have an account? Log in