Table of Contents

1. What is Sorting? Why Does It Matter?

2. Big-O Notation — Measuring Algorithm Speed

3. Bubble Sort — The Beginner's Sort

4. Selection Sort — Find Minimum, Place It

5. Insertion Sort — Like Sorting Playing Cards

6. Merge Sort — Divide, Sort, Merge

7. Quick Sort — The Fastest in Practice

8. Heap Sort — Using a Binary Heap

9. Counting, Radix & Bucket Sort — Linear Sorts

10. Linear Search — Check Every Element

11. Binary Search — Divide and Conquer Search

12. Complexity Comparison Table

13. Java Built-in Sorting

14. Interview Questions & Answers (30+ Q&A;)

Chapter 1: What is Sorting? Why Does It
Matter?
Sorting means arranging elements in a specific order — usually ascending (small to large) or
descending (large to small). It's one of the most fundamental operations in computer science.

Hinglish: Sorting matlab data ko order mein lagana. Jaise library mein books alphabetically rakhi hoti
hain, phone contacts A-Z hote hain, leaderboard marks ke hisaab se hota hai — yahi sorting hai! Sorted
data ke saath kaam karna bahut aasaan ho jaata hai.

Why is Sorting So Important?

✓ Faster Searching: Binary Search only works on sorted data — O(log n) vs O(n). Sorted data =
1000x faster search!

✓ Better Performance: Many algorithms work better on sorted data — finding duplicates, merging lists,
database queries.

✓ Data Presentation: Leaderboards, product listings, search results — all require sorted data for good
UX.

✓ Foundation for Bigger Problems: Sorting is used inside many complex algorithms — graph
algorithms, string matching, etc.

✓ Interviews!: Every DSA interview asks sorting questions. Understanding sorting shows you
understand algorithms deeply.

Two Types of Sorting

Type Description Examples

Elements compared with each Bubble, Selection, Insertion,

Comparison-based
other using <, >, = operators Merge, Quick, Heap

No direct comparison — use Counting Sort, Radix Sort, Bucket

Non-comparison based
counting or digit tricks Sort

KEY FACT The best possible comparison-based sort is O(n log n). This is mathematically proven —
you cannot sort by comparing elements faster than this. Non-comparison sorts can achieve O(n) but
need special conditions (integer data, bounded range).

Sorting & Searching Algorithms — Complete DSA Guide | Page 2

Chapter 2: Big-O Notation — Measuring
Speed
Big-O notation describes how an algorithm's runtime grows as the input size (n) grows. It helps us
compare algorithms without running them.

Hinglish: Big-O matlab "agar n double ho jaaye toh kitna time zyada lagega?" O(n) matlab n double →
time double. O(n²) matlab n double → time 4x. O(log n) matlab n double → time sirf +1 step! Algorithm
choose karte waqt yahi sochna hai.

Big-O Name n=100 example n=1000 example Speed

O(1) Constant 1 op 1 op ■ Instant

O(log n) Logarithmic 7 ops 10 ops ■ Very Fast

O(n) Linear 100 ops 1,000 ops ■ Fast

O(n log n) Linearithmic 700 ops 10,000 ops ■ Good

O(n²) Quadratic 10,000 ops 1,000,000 ops ■ Slow

O(2■) Exponential 10³■ ops Impossible ■ Unusable

INTERVIEW TIP What to say in interviews: Always mention Best Case, Average Case, and Worst
Case. For example: Quick Sort is O(n log n) average but O(n²) worst case (when already sorted and
pivot is always last element). Merge Sort is always O(n log n) — guaranteed!

Sorting & Searching Algorithms — Complete DSA Guide | Page 3

Chapter 3: Bubble Sort
Bubble Sort is the simplest sorting algorithm. It repeatedly compares adjacent elements and swaps
them if they are in the wrong order. The largest element "bubbles up" to the end in each pass.

Hinglish: Bubble Sort ek soda bottle jaisa hai — bade bubbles upar aajaate hain! Har pass mein sabse
bada element sahi jagah pe pahunch jaata hai. Jaise queue mein sab log adjust karte hain — agar koi
bada hai peeche wale se, toh swap karo.

Pass 1: Compare [0] and [1] → 64>34 → SWAP

■
64 34 25 12 22 11

Pass 1: Compare [1] and [2] → 64>25 → SWAP

■
34 64 25 12 22 11

Pass 1 done: 64 bubbled to correct position!

34 25 12 22 11 64

SORTED! Largest always bubbles to end each pass

11 12 22 25 34 64
Bubble Sort: largest element "bubbles up" to end in each pass

Fig 3.1: Each pass moves the largest unsorted element to its correct position at the end

Step-by-Step Trace
Array: [64, 34, 25, 12, 22, 11]

Pass 1: Compare adjacent pairs, swap if left > right

[64,34] → swap → [34,64,25,12,22,11]

[64,25] → swap → [34,25,64,12,22,11]

[64,12] → swap → [34,25,12,64,22,11]

[64,22] → swap → [34,25,12,22,64,11]

[64,11] → swap → [34,25,12,22,11,64] ← 64 is in final position!

Pass 2: Repeat for first 5 elements

... 34 bubbles to position 5

Sorting & Searching Algorithms — Complete DSA Guide | Page 4

After 5 passes: [11,12,22,25,34,64] SORTED!

Java Code
public static void bubbleSort(int[] arr) {

int n = [Link];

boolean swapped; // optimization flag

for (int pass = 0; pass < n - 1; pass++) {

swapped = false;

// Last "pass" elements are already sorted

for (int j = 0; j < n - 1 - pass; j++) {

if (arr[j] > arr[j + 1]) {

// Swap arr[j] and arr[j+1]

int temp = arr[j];

arr[j] = arr[j + 1];

arr[j + 1] = temp;

swapped = true;

// If no swap in this pass → array is already sorted!

if (!swapped) break; // Early exit optimization

// Time: Best O(n) [already sorted] | Average/Worst O(n²)

// Space: O(1) — in-place sorting

// Stable: YES — equal elements maintain relative order

Sorting & Searching Algorithms — Complete DSA Guide | Page 5

 Case Time Complexity When

Array already sorted (with

Best O(n)
swapped flag optimization)

Average O(n²) Random input

Worst O(n²) Array sorted in reverse order

Space O(1) In-place — no extra array needed

WHEN TO USE When to use Bubble Sort: Almost never in production! Only useful for teaching
purposes and when array is nearly sorted (best case O(n) with optimization). For real problems, use
Merge Sort or Quick Sort.

Sorting & Searching Algorithms — Complete DSA Guide | Page 6

Chapter 4: Selection Sort
Selection Sort divides the array into two parts — sorted (left) and unsorted (right). In each pass, it
finds the minimum element from the unsorted part and places it at the beginning of the unsorted
portion.

Hinglish: Selection Sort ek topper student jaisa hai — pehle poori class mein sabse kam marks wala
dhundho, usse pehle position pe rakho. Phir baaki class mein se minimum dhundho, doosri position pe
rakho. Baar baar minimum select karo, isliye "Selection" Sort!

POSwith index 0
Pass 1: Find min in [0..4] → 11 at index 4 → swap MIN
64 25 12 22 11

Pass 2: Find min in [1..4] → 12 at index 2 → swap with index

POS1 MIN
11 25 12 22 64

Pass 3: Find min in [2..4] → 22 at index 3 → swap with index 2 POS MIN
11 12 25 22 64

SORTED! Each pass finds minimum and places it correctly.

11 12 22 25 64
Selection Sort: find minimum → place at front → repeat for rest

Fig 4.1: Orange=current position, Red=minimum found, Green=sorted portion

Java Code
public static void selectionSort(int[] arr) {

int n = [Link];

for (int i = 0; i < n - 1; i++) {

// Find minimum in unsorted portion arr[i..n-1]

int minIdx = i;

for (int j = i + 1; j < n; j++) {

if (arr[j] < arr[minIdx]) {

minIdx = j; // update index of minimum

Sorting & Searching Algorithms — Complete DSA Guide | Page 7

// Swap minimum with first element of unsorted portion

if (minIdx != i) {

int temp = arr[minIdx];

arr[minIdx] = arr[i];

arr[i] = temp;

// Time: Always O(n²) — no best case improvement

// Space: O(1) — in-place

// Stable: NO — relative order of equal elements may change

// Swaps: O(n) — very few swaps! Good when write cost is high

KEY INSIGHT Key advantage of Selection Sort: It makes at most O(n) swaps, unlike Bubble Sort
which can make O(n²) swaps. When data write is expensive (e.g., memory wear on SSDs), fewer swaps
= better. But time is always O(n²) regardless.

Sorting & Searching Algorithms — Complete DSA Guide | Page 8

Chapter 5: Insertion Sort
Insertion Sort builds the sorted array one element at a time. It takes each element from the unsorted
portion and inserts it into its correct position in the sorted portion by shifting larger elements right.

Hinglish: Insertion Sort bilkul waise hai jaise tum taash (playing cards) sort karte ho haath mein. Ek card
uthao, dekho kahan fit hota hai sorted portion mein, baaki cards seedhe karo, card daalo. Ek ek card
uthate rehte ho jab tak sab sort nahi ho jaate!

Key=3: Compare with 5 → 5>3 → shift 5 right, insert 3

5 3 8 1 9 2

Key=8: 8>5 → stays. [3,5,8] sorted.

3 5 8 1 9 2

Key=1: shift 8,5,3 right → insert 1 at beginning

3 5 8 1 9 2

Key=2: shift 9,8,5,3 right → insert 2. Almost done!

1 3 5 8 9 2

SORTED! Like sorting playing cards in hand one by one.

1 2 3 5 8 9
Green = sorted portion | Red = key being inserted | Blue = unsorted

Fig 5.1: Dark green=sorted portion, red=key being inserted, blue=unsorted

Java Code
public static void insertionSort(int[] arr) {

int n = [Link];

for (int i = 1; i < n; i++) {

int key = arr[i]; // element to insert

int j = i - 1;

// Shift elements greater than key to the right

while (j >= 0 && arr[j] > key) {

arr[j + 1] = arr[j]; // shift right

j--;

Sorting & Searching Algorithms — Complete DSA Guide | Page 9

arr[j + 1] = key; // insert key in correct position

// Example trace: [5, 3, 8, 1]

// i=1: key=3, shift 5 right → [5,5,8,1] → insert → [3,5,8,1]

// i=2: key=8, no shift needed → [3,5,8,1]

// i=3: key=1, shift 8,5,3 → insert → [1,3,5,8]

// Time: Best O(n) [sorted] | Worst O(n²) [reverse sorted]

// Space: O(1) | Stable: YES

WHEN TO USE When to use Insertion Sort: (1) Small arrays (n < 20) — very fast in practice, (2)
Nearly sorted arrays — best case O(n), (3) Online sorting — elements arrive one by one. Java's TimSort
uses Insertion Sort for small subarrays!

Sorting & Searching Algorithms — Complete DSA Guide | Page 10

Chapter 6: Merge Sort — Divide, Sort, Merge
Merge Sort is a classic Divide and Conquer algorithm. It splits the array in half recursively until each
subarray has 1 element (already sorted), then merges them back in sorted order.

Hinglish: Merge Sort ek "divide and rule" strategy hai. Problem bahut badi hai → do hisson mein baanto
→ har hissa sort karo → phir dono sorted halves ko merge karo. Yeh ek chef jaisa hai jo bada khana
banane ke liye apni team ko alag alag kaam deta hai aur baad mein sab combine karta hai!

38 27 43 3 9 82 10
Original Array

38 27 43 3 9 82 10
Left half Right half

38 27 43 3 9 82 10
[38] [27,43] [3,9] [82,10]

27 38 43 3 9 10 82
Merge → sorted Merge → sorted

3 9 10 27 38 43 82
Final Merge → SORTED!
DIVIDE → CONQUER → MERGE
Merge Sort: split in half until 1 element, then merge in sorted order

Fig 6.1: Merge Sort splits down to single elements, then merges back in sorted order

Java Code
public static void mergeSort(int[] arr, int left, int right) {

if (left >= right) return; // base case: 1 element

int mid = left + (right - left) / 2; // avoid overflow

mergeSort(arr, left, mid); // sort left half

mergeSort(arr, mid + 1, right); // sort right half

merge(arr, left, mid, right); // merge both halves

private static void merge(int[] arr, int left, int mid, int right) {

Sorting & Searching Algorithms — Complete DSA Guide | Page 11

int n1 = mid - left + 1;

int n2 = right - mid;

int[] L = new int[n1]; // temp left array

int[] R = new int[n2]; // temp right array

// Copy data to temp arrays

for (int i = 0; i < n1; i++) L[i] = arr[left + i];

for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j];

int i = 0, j = 0, k = left;

// Merge: pick smaller element from L or R

while (i < n1 && j < n2) {

if (L[i] <= R[j]) arr[k++] = L[i++];

else arr[k++] = R[j++];

// Copy remaining elements

while (i < n1) arr[k++] = L[i++];

while (j < n2) arr[k++] = R[j++];

// Call: mergeSort(arr, 0, [Link] - 1)

// Time: Always O(n log n) — guaranteed! Best choice for linked lists.

// Space: O(n) — needs extra array for merging

// Stable: YES

WHEN TO USE Merge Sort is the best choice when: (1) Stability is required, (2) Sorting linked lists
(no random access — merge sort doesn't need it), (3) External sorting (data too large for RAM — read
from disk in chunks). Guaranteed O(n log n) — no worst case.

Sorting & Searching Algorithms — Complete DSA Guide | Page 12

Chapter 7: Quick Sort — The Fastest in
Practice
Quick Sort is the most widely used sorting algorithm. It picks a pivot element, partitions the array so
all elements smaller than pivot go left and larger go right, then recursively sorts both sides.

Hinglish: Quick Sort ek leader (pivot) choose karta hai. Phir sab chhote log left side mein jaate hain, sab
bade log right side. Leader apni perfect position pe aa jaata hai. Phir left aur right groups mein yahi
process repeat hoti hai — har baar ek leader apni jagah fix ho jaata hai!

Pick pivot = 70 (last). i starts at -1. PIVOT

10 80 30 90 40 50 70

Elements < pivot go left, > pivot go right PIVOT

10 30 40 50 80 90 70

Pivot 70 placed correctly! Recurse left and right sides

10 30 40 50 70 80 90
Orange=pivot | Green=less than pivot | Red=greater than pivot

Fig 7.1: Orange=pivot, Green=less than pivot (correct side), Red=greater than pivot

Java Code
public static void quickSort(int[] arr, int low, int high) {

if (low < high) {

int pivotIdx = partition(arr, low, high);

quickSort(arr, low, pivotIdx - 1); // sort left of pivot

quickSort(arr, pivotIdx + 1, high); // sort right of pivot

private static int partition(int[] arr, int low, int high) {

int pivot = arr[high]; // choose last element as pivot

int i = low - 1; // i = index of smaller element

Sorting & Searching Algorithms — Complete DSA Guide | Page 13

 for (int j = low; j < high; j++) {

if (arr[j] <= pivot) {

i++;

// swap arr[i] and arr[j]

int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;

// Place pivot in correct position

int temp = arr[i + 1]; arr[i + 1] = arr[high]; arr[high] = temp;

return i + 1; // return pivot index

// Call: quickSort(arr, 0, [Link] - 1)

// Time: Best/Average O(n log n) | Worst O(n²) [sorted array, bad pivot]

// Space: O(log n) average [recursive call stack]

// Stable: NO

// Pivot selection strategies:

// 1. Last element (above) — simple but bad for sorted input

// 2. Random pivot — arr[low + [Link](high-low+1)] — recommended!

// 3. Median of three — median of first, mid, last — most practical

Pivot Choice Worst Case Scenario Recommendation

Always last element Already sorted array → O(n²) Avoid for production

Random element Very unlikely O(n²) Good choice, add randomization

Median of three Very unlikely O(n²) Best practical choice

REAL WORLD Quick Sort in practice: Despite O(n²) worst case, Quick Sort is the fastest sorting
algorithm in practice for random data because of excellent cache performance (in-place, contiguous
memory access). Java's [Link]() uses Dual-Pivot QuickSort for primitives!

Sorting & Searching Algorithms — Complete DSA Guide | Page 14

Chapter 8: Heap Sort — Using a Binary
Heap
Heap Sort uses a special tree structure called a Binary Heap. First it builds a Max-Heap (largest
element at root), then repeatedly extracts the maximum and places it at the end.

Hinglish: Heap Sort ek president election jaisa hai. Pehle sabse bade candidate ko top pe laao (build
max heap). Phir wo retire hota hai — end mein jaata hai. Ab baaki mein se naya president chunte hain —
phir retire. Baar baar yahi process jab tak sab sorted na ho jaayein!

Max-Heap: Parent always >= Children. Root = Maximum (RED)

90

80 70

50 60 30 40

Array representation:
90 80 70 50 60 30 40
[0] [1] [2] [3] [4] [5] [6]

Parent of i = (i-1)/2

Left child = 2i+1 Heap Sort: Build max-heap → swap root with last → heapify → repeat

Right child =Fig 8.1: Max-Heap structure — parent always >= children. Root is always maximum.
2i+2

Java Code
public static void heapSort(int[] arr) {

int n = [Link];

// Step 1: Build Max-Heap

// Start from last non-leaf node and heapify down

for (int i = n / 2 - 1; i >= 0; i--)

heapify(arr, n, i);

// Step 2: Extract max one by one

Sorting & Searching Algorithms — Complete DSA Guide | Page 15

for (int i = n - 1; i > 0; i--) {

// Swap root (max) with last element

int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp;

// Heapify the reduced heap

heapify(arr, i, 0);

private static void heapify(int[] arr, int n, int i) {

int largest = i; // assume root is largest

int left = 2 * i + 1; // left child

int right = 2 * i + 2; // right child

// If left child > largest

if (left < n && arr[left] > arr[largest]) largest = left;

// If right child > largest

if (right < n && arr[right] > arr[largest]) largest = right;

// If root is not largest, swap and continue heapifying

if (largest != i) {

int temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp;

heapify(arr, n, largest); // recursive heapify

// Time: Always O(n log n) — guaranteed like Merge Sort

// Space: O(1) — in-place (unlike Merge Sort which needs O(n))

// Stable: NO

Sorting & Searching Algorithms — Complete DSA Guide | Page 16

Chapter 9: Counting, Radix & Bucket Sort
These are non-comparison based sorts that can achieve O(n) linear time by exploiting properties of
the data. They don't compare elements directly!

Counting Sort — For Small Integer Ranges

Count the frequency of each element, then use cumulative count to place elements in sorted position.
Works only for non-negative integers in a known range.

Hinglish: Socho class mein grades A,B,C,D hain. Count karo kitne A hain, kitne B, kitne C, kitne D. Phir
list mein pehle saare A, phir saare B — sorted! Koi comparison nahi, sirf count!

public static void countingSort(int[] arr) {

int max = [Link](arr).max().getAsInt();

int[] count = new int[max + 1]; // count array

// Step 1: Count each element

for (int val : arr) count[val]++;

// Example: arr=[4,2,2,8,3,3,1] → count=[0,1,2,2,1,0,0,0,1]

// Step 2: Cumulative count (prefix sum)

for (int i = 1; i < [Link]; i++)

count[i] += count[i - 1];

// Step 3: Build output array (traverse original in reverse for stability)

int[] output = new int[[Link]];

for (int i = [Link] - 1; i >= 0; i--) {

output[count[arr[i]] - 1] = arr[i];

count[arr[i]]--;

[Link](output, 0, arr, 0, [Link]);

// Time: O(n + k) where k = range of input | Space: O(k)

Sorting & Searching Algorithms — Complete DSA Guide | Page 17

 // Best for: exam scores, ages, small integer data

Radix Sort — Digit by Digit

Sort numbers digit by digit from least significant to most significant digit using Counting Sort as a
subroutine.

// Example: arr = [170, 45, 75, 90, 802, 24, 2, 66]

// Step 1: Sort by ones digit

// [170, 90, 802, 2, 24, 45, 75, 66]

// Step 2: Sort by tens digit

// [802, 2, 24, 45, 66, 170, 75, 90]

// Step 3: Sort by hundreds digit

// [2, 24, 45, 66, 75, 90, 170, 802] ← SORTED!

// Time: O(d * (n + k)) where d = digits, k = base (10)

// Effectively O(n) for fixed-size integers

// Use for: large numbers, phone numbers, zip codes

Bucket Sort — Range-Based Buckets

Distribute elements into "buckets" based on their range, sort each bucket (with insertion sort), then
concatenate.

// Best for: uniformly distributed floating point in [0, 1)

// Example: [0.897, 0.565, 0.656, 0.123, 0.665, 0.343]

// Bucket 0: [0.0-0.2) → [0.123]

// Bucket 3: [0.6-0.8) → [0.656, 0.665] ← sort within bucket

// Concatenate all buckets → sorted!

// Time: O(n) average | O(n²) worst case

// Use for: floating point data, when distribution is uniform

Sorting & Searching Algorithms — Complete DSA Guide | Page 18

Chapter 10: Linear Search
Linear Search (also called Sequential Search) checks every element one by one from left to right until
it finds the target or reaches the end.

Hinglish: Linear Search ek lost key dhundne jaisa hai — ghar ka har kamra check karo ek ek karke jab
tak key na mile. Simple hai lekin slow! Agar 1000 rooms hain aur key last room mein hai toh 1000 baar
check karna padega!

Linear Search: Find 22 in array

Step 1: Check [0]=64 → ✗ Not target, move right

64 34 25 12 22 11 90
■

Step 2: Check [1]=34 → ✗ Not target, move right

64 34 25 12 22 11 90
■

Step 3: Check [2]=25 → ✗ Not target, move right

64 34 25 12 22 11 90
■

Step 4: Check [3]=12 → ✗ Not target, move right

64 34 25 12 22 11 90
■
Step 5: Check [4]=22 → ✓ FOUND at index 4!

64 Linear 34 25EVERY element

Search: Check 12 from left22 11 O(n)
to right until found. 90
✓
Fig 10.1: Linear Search checks each element from left — orange=current check, red=not found, green=found!

Java Code
public static int linearSearch(int[] arr, int target) {

for (int i = 0; i < [Link]; i++) {

if (arr[i] == target) {

return i; // return index where found

return -1; // not found

Sorting & Searching Algorithms — Complete DSA Guide | Page 19

// Time: Best O(1) [target at index 0]

// Average O(n/2) = O(n)

// Worst O(n) [target at end or not present]

// Space: O(1)

// Works on: UNSORTED and sorted arrays

// Works with: any data type that supports equals()

// For objects:

public static int linearSearch(String[] arr, String target) {

for (int i = 0; i < [Link]; i++)

if (arr[i].equals(target)) return i;

return -1;

// When to use: small arrays, unsorted data, one-time search

WHEN TO USE Advantages of Linear Search: Works on unsorted data. Works with any data type.
Simple to implement. For very small arrays (< 10 elements), faster than Binary Search in practice due to
no setup cost.

Sorting & Searching Algorithms — Complete DSA Guide | Page 20

Chapter 11: Binary Search — O(log n)
Power!
Binary Search works on sorted arrays by repeatedly halving the search space. It compares the target
with the middle element — if equal, found! If target is smaller, search left half. If larger, search right half.

Hinglish: Binary Search bilkul dictionary use karne jaisa hai. Page 500 kholo — word "apple" se pehle
hai toh pehli 500 pages mein dekho, nahi toh last 500 mein. Phir aadha again. Baar baar aadha karte
rehte hain jab tak word mile! 1000 pages ki dictionary mein sirf 10 steps lagenge!

Binary Search: Find 23 in SORTED array

Step 1: low=0, high=9, mid=4, arr[4]=16. 23>16 → search RIGHT half

2 5 8 12 16 23 38 56 72 91
MID
[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]
low high

Step 2: low=5, high=9, mid=7, arr[7]=56. 23<56 → search LEFT half

2 5 8 12 16 23 38 56 72 91
MID
[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]
low high

Step 3: low=5, high=6, mid=5, arr[5]=23 = TARGET! FOUND at index 5!

2 5 8 12 16 23 38 56 72 91
MID
[0] [1] [2] [3] [4] [5] [6] [7] [8] [9]
low high

Binary Search eliminates HALF the array each step → O(log n) — much faster!

Fig 11.1: Binary Search eliminates half the remaining elements each step — O(log n)

Iterative Binary Search — Java Code

public static int binarySearch(int[] arr, int target) {

int low = 0;

int high = [Link] - 1;

while (low <= high) {

int mid = low + (high - low) / 2; // avoid integer overflow!

// NOT: mid = (low + high) / 2 ← can overflow for large arrays

Sorting & Searching Algorithms — Complete DSA Guide | Page 21

 if (arr[mid] == target) {

return mid; // FOUND!

} else if (arr[mid] < target) {

low = mid + 1; // target is in RIGHT half

} else {

high = mid - 1; // target is in LEFT half

return -1; // not found

// Time: Best O(1) | Average O(log n) | Worst O(log n)

// Space: O(1) iterative / O(log n) recursive [call stack]

// REQUIRES: sorted array!

Recursive Binary Search

public static int binarySearchRecursive(int[] arr, int low, int high, int target) {

if (low > high) return -1; // base case: not found

int mid = low + (high - low) / 2;

if (arr[mid] == target) return mid;

if (arr[mid] < target) return binarySearchRecursive(arr, mid+1, high, target);

return binarySearchRecursive(arr, low, mid-1, target);

// Call: binarySearchRecursive(arr, 0, [Link]-1, target)

Binary Search Variations — Important for Interviews!

// Find FIRST occurrence of target (duplicates exist)

public static int firstOccurrence(int[] arr, int target) {

Sorting & Searching Algorithms — Complete DSA Guide | Page 22

int low = 0, high = [Link] - 1, result = -1;

while (low <= high) {

int mid = low + (high - low) / 2;

if (arr[mid] == target) { result = mid; high = mid - 1; } // keep searching LEFT

else if (arr[mid] < target) low = mid + 1;

else high = mid - 1;

return result;

// Find LAST occurrence

public static int lastOccurrence(int[] arr, int target) {

int low = 0, high = [Link] - 1, result = -1;

while (low <= high) {

int mid = low + (high - low) / 2;

if (arr[mid] == target) { result = mid; low = mid + 1; } // keep searching RIGHT

else if (arr[mid] < target) low = mid + 1;

else high = mid - 1;

return result;

// Find floor (largest element <= target)

// Find ceil (smallest element >= target)

// Search in rotated sorted array → classic interview question!

// Java built-in binary search:

int idx = [Link](arr, target);

// Returns index if found, else -(insertion_point) - 1

Sorting & Searching Algorithms — Complete DSA Guide | Page 23

Chapter 12: Complexity Comparison

Algorithm Complexity Comparison

Algorithm Best Worst Space Stable

Bubble Sort O(n²) O(n²) O(1) Stable

Selection Sort O(n²) O(n²) O(1) Unstable

Insertion Sort O(n) O(n²) O(1) Stable

Merge Sort O(n log n) O(n log n) O(n) Stable

Quick Sort O(n log n) O(n²) O(log n) Unstable

Heap Sort O(n log n) O(n log n) O(1) Unstable

Counting Sort O(n+k) O(n+k) O(k) Stable

Linear Search O(1) O(n) O(1) N/A

Binary Search O(1) O(log n) O(1) N/A

Green = good, Red = slow, Yellow = depends on input

Fig 12.1: Full complexity comparison — Green=good, Red=slow, Yellow=depends

Which Algorithm to Choose?

Situation Best Choice Why

Small array (n < 20) Insertion Sort Low overhead, fast in practice

Nearly sorted data Insertion Sort O(n) best case

Best cache performance in

General purpose, speed Quick Sort
practice

Guaranteed O(n log n) Merge Sort No worst case degradation

No extra memory allowed Heap Sort O(1) space, O(n log n) time

Stable: preserves equal element

Stability required Merge Sort / Insertion Sort
order

Linked list Merge Sort No random access needed

Integer data, small range Counting Sort O(n+k) linear time!

Large integers, multiple keys Radix Sort Digit by digit, stable

Sorting & Searching Algorithms — Complete DSA Guide | Page 24

 Situation Best Choice Why

O(log n) — eliminate half each

Searching in sorted array Binary Search
step

Searching in unsorted array Linear Search Only option, O(n)

Sorting & Searching Algorithms — Complete DSA Guide | Page 25

Chapter 13: Java Built-in Sorting
Java provides highly optimised built-in sorting methods. In real projects and competitive programming,
always use these instead of implementing from scratch.

[Link]() — For Arrays

import [Link];

// Primitive arrays — uses Dual-Pivot QuickSort (O(n log n))

int[] nums = {5, 2, 8, 1, 9};

double[] doubles = {3.1, 1.5, 2.7};

[Link](nums); // [1, 2, 5, 8, 9]

[Link](doubles); // [1.5, 2.7, 3.1]

// Sort a PORTION of array

[Link](nums, 1, 4); // sorts indices 1,2,3 only (fromIndex inclusive, toIndex

exclusive)

// Object arrays — uses TimSort (stable, O(n log n))

String[] names = {"Charlie", "Alice", "Bob"};

[Link](names); // ["Alice", "Bob", "Charlie"]

// Sort with custom Comparator (only for Object arrays, not primitives)

Integer[] arr = {5, 2, 8, 1, 9};

[Link](arr, [Link]()); // [9, 8, 5, 2, 1]

// Sort 2D array by first column

int[][] matrix = {{3,1},{1,4},{2,2}};

[Link](matrix, (a, b) -> a[0] - b[0]); // sort by matrix[i][0]

// [[1,4],[2,2],[3,1]]

// Sort by length of strings

String[] words = {"banana","kiwi","apple","fig"};

Sorting & Searching Algorithms — Complete DSA Guide | Page 26

 [Link](words, [Link](String::length));

// ["fig","kiwi","apple","banana"]

[Link]() — For Lists

import [Link];

List<Integer> list = new ArrayList<>([Link](5, 2, 8, 1, 9));

[Link](list); // [1, 2, 5, 8, 9]

[Link](list, [Link]()); // [9, 8, 5, 2, 1]

// [Link]() (Java 8+) — same thing, cleaner syntax

[Link]([Link]());

[Link]((a, b) -> b - a); // reverse order using lambda

// Sort list of custom objects

List<Student> students = new ArrayList<>();

[Link](new Student("Roshan", 90));

[Link](new Student("Priya", 85));

// By marks ascending

[Link]([Link](s -> [Link]));

// By name, then by marks if name is same

[Link]([Link]((Student s) -> [Link])

.thenComparingInt(s -> [Link]));

TIMSORT FACT Java's TimSort: Java uses TimSort for object arrays and Collections. TimSort is a
hybrid of Merge Sort and Insertion Sort. It detects already-sorted "runs" and uses Insertion Sort for small
arrays. It is stable, O(n log n) worst case, O(n) best case. Best sorting algorithm for real-world data!

Sorting & Searching Algorithms — Complete DSA Guide | Page 27

Chapter 14: Interview Questions & Answers
These 30+ questions cover everything asked in campus placements, coding interviews, and product
company rounds. Every answer is detailed and interview-ready!

Sorting Questions

Q: What is the difference between stable and unstable sorting algorithms?

A: A STABLE sort preserves the relative order of elements that are equal. If two elements have the same
key, their original order is maintained in the output. UNSTABLE sort may change the relative order of
equal elements. Stable: Bubble Sort, Insertion Sort, Merge Sort, Counting Sort, TimSort. Unstable:
Selection Sort, Quick Sort, Heap Sort. Stability matters when: sorting objects by multiple keys (sort by
marks, then by name — must be stable for the second sort to work correctly).

Q: Which sorting algorithm is best? Why does it depend?

A: There is no single "best" algorithm — it depends on the use case: Quick Sort: fastest in practice for
random data (cache-friendly, in-place). Merge Sort: when stability required, guaranteed O(n log n), or
sorting linked lists. Insertion Sort: small arrays (< 20), nearly sorted data. Heap Sort: when O(1) space is
required with O(n log n) time. Counting/Radix Sort: when data is integers in a known range — beats O(n
log n)! Java uses Dual-Pivot QuickSort for primitives and TimSort for objects.

Q: What is the time complexity of Merge Sort? Why is it always O(n log n)?

A: Merge Sort is always O(n log n) for best, average, and worst case. The array is divided into halves: log
n levels of division. At each level, we merge n total elements: O(n) work per level. Total: O(n) × O(log n) =
O(n log n). This never degrades because the split is always in half — no pivot selection problem. Space:
O(n) extra for the temporary merge arrays. This guaranteed performance makes it preferred for external
sorting.

Sorting & Searching Algorithms — Complete DSA Guide | Page 28

Q: Why is Quick Sort O(n²) in the worst case? How to avoid it?

A: Worst case occurs when pivot is always the minimum or maximum element — creating partitions of size
0 and n-1. Example: sorted array with last element as pivot → n levels deep × O(n) per level = O(n²).
Avoidance strategies: (1) Random pivot: arr[low + [Link](high-low+1)] — makes worst case
extremely unlikely. (2) Median of three: choose median of first, middle, last elements. (3) Dual-pivot
(Java's implementation): use two pivots to create three partitions. With random pivot, expected time is O(n
log n) with very high probability.

Q: What is the difference between Quick Sort and Merge Sort?

A: Quick Sort: In-place (O(log n) stack space), unstable, average O(n log n), worst O(n²). Pivot-based
partitioning. Faster in practice due to cache efficiency. Merge Sort: O(n) extra space, stable, always O(n
log n). Divide by half, merge step required. Better for linked lists and when stability needed. Key difference:
Quick Sort does work during partitioning (before recursion). Merge Sort does work during merging (after
recursion). Java uses Quick Sort for primitives (stability not needed) and TimSort (Merge+Insertion) for
objects.

Q: Explain Heap Sort. What is a Max-Heap?

A: A Max-Heap is a complete binary tree where every parent >= both children. Root is always the
maximum element. Array representation: parent(i) = (i-1)/2, left(i) = 2i+1, right(i) = 2i+2. Heap Sort steps:
(1) Build Max-Heap from array (O(n) — heapify from last non-leaf). (2) Repeat n-1 times: swap root (max)
with last element, reduce heap size by 1, heapify root. Each extraction puts one element in its final sorted
position. Time: O(n log n) always. Space: O(1) in-place. Unstable.

Q: What is the lower bound for comparison-based sorting?

A: The theoretical lower bound for comparison-based sorting is Ω(n log n). Proof: Any comparison-based
sort can be modelled as a decision tree. For n elements, there are n! possible orderings (leaf nodes).
Height of tree ≥ log■(n!) ≈ n log n (by Stirling's approximation). Therefore, we need at least n log n
comparisons in the worst case. This means NO comparison-based sort can be faster than O(n log n) in the
worst case — ever. Counting, Radix, Bucket sort beat this by NOT using comparisons!

Sorting & Searching Algorithms — Complete DSA Guide | Page 29

Q: How does Counting Sort work and when is it used?

A: Counting Sort counts the frequency of each element, computes prefix sums for positions, then places
each element in its correct position. Steps: (1) Find max, create count array of size max+1. (2) Count
occurrences. (3) Compute cumulative sum (gives final positions). (4) Build output by traversing input in
reverse (for stability). Time: O(n+k) where k = range of values. Space: O(n+k). Use when: data is integers,
range k is small (k ≈ n). Not suitable for large ranges (floating point, negative numbers need modifications).

Q: What is the difference between in-place and out-of-place sorting?

A: In-place: uses only O(1) extra space (constant, regardless of n). Examples: Bubble Sort, Selection Sort,
Insertion Sort, Heap Sort, Quick Sort. Out-of-place: uses O(n) or more extra space. Examples: Merge Sort
(O(n) for temp arrays), Counting Sort (O(k)), Radix Sort. In-place is preferred when memory is limited.
Out-of-place often achieves better or guaranteed time complexity (Merge Sort).

Q: What sorting algorithm would you use for sorting a linked list?

A: Merge Sort is the best choice for linked lists. Why: Merge Sort doesn't require random access — it
always moves sequentially. Splitting a linked list is easy (find middle with slow/fast pointer). Merging two
sorted linked lists is O(n) and done in-place (just redirect pointers, no extra array). Quick Sort on linked list
needs random pivot access which is O(n). Heap Sort requires random access by index — doesn't work on
linked lists. Merge Sort on linked list: Time O(n log n), Space O(log n) [recursive stack only].

Searching Questions

Q: What is Binary Search and what is its prerequisite?

A: Binary Search is a search algorithm that finds a target in a SORTED array by repeatedly halving the
search space. Prerequisite: array MUST be sorted. Process: compare target with middle element. If equal
→ found. If target < middle → search left half. If target > middle → search right half. Time: O(log n) —
eliminates half the elements each step. For n=1,000,000: linear search worst case = 1,000,000 steps.
Binary search worst case = only 20 steps! That's the power of O(log n).

Sorting & Searching Algorithms — Complete DSA Guide | Page 30

Q: Why do we write mid = low + (high - low) / 2 and not mid = (low + high) / 2?

A: Integer overflow! In Java, int has max value = 2,147,483,647. If low = 1,500,000,000 and high =
2,000,000,000: low + high = 3,500,000,000 → overflows int range → negative result → wrong mid! low +
(high - low) / 2 = 1,500,000,000 + 250,000,000 = 1,750,000,000 → correct. This is a subtle but critical bug
in many implementations. Always use: mid = low + (high - low) / 2.

Q: What is the difference between Linear Search and Binary Search?

A: Linear Search: works on unsorted or sorted data. Time O(n). Space O(1). Check each element one by
one from left. Simple, no requirement. Binary Search: requires SORTED data. Time O(log n). Space O(1)
iterative. Eliminates half the search space each step. Much faster for large arrays. When to use Linear:
data is unsorted, small array, only one search needed, or searching by complex criteria that can't be
sorted. When to use Binary: sorted data, multiple searches on same data, or after sorting (sort + binary
search can be faster than n linear searches).

Q: How would you find an element in a rotated sorted array?

A: A rotated sorted array like [4,5,6,7,0,1,2] can be searched with modified Binary Search. Key insight: in a
rotated array, at least ONE half is always sorted. Algorithm: find mid. Check which half is sorted (compare
arr[low] with arr[mid]). If left half sorted (arr[low] <= arr[mid]): check if target in arr[low..mid]. If yes →
search left. If no → search right. Else right half is sorted: check if target in arr[mid..high]. Same logic. Time:
O(log n). This is a classic Google/Amazon interview question!

Q: What is a Binary Search Tree (BST) and how does it differ from Binary Search?

A: Binary Search is an algorithm applied to a sorted ARRAY. Binary Search Tree (BST) is a DATA
STRUCTURE (tree) where: left subtree contains only nodes < current node, right subtree contains only
nodes > current node. BST search: start at root, go left if target < node, right if target > node. BST average
search: O(log n) for balanced tree, O(n) for skewed tree. Difference: Binary Search on array is always
O(log n). BST depends on whether it's balanced (use AVL Tree or Red-Black Tree for guaranteed O(log
n)).

Sorting & Searching Algorithms — Complete DSA Guide | Page 31

Q: How many comparisons does Binary Search need for n=1,000,000?

A: Binary Search needs at most log■(n) + 1 comparisons. log■(1,000,000) = log■(2²■) ≈ 20. So at most
21 comparisons to search 1 million elements! Compare: Linear Search needs up to 1,000,000
comparisons. This illustrates the massive difference between O(n) and O(log n). Each doubling of n only
adds 1 more step for Binary Search — it scales incredibly well.

Q: What is Interpolation Search and when is it better than Binary Search?

A: Interpolation Search is an improvement of Binary Search for uniformly distributed sorted data. Instead
of always checking the middle, it estimates where the target likely is: pos = low + ((target - arr[low]) /
(arr[high] - arr[low])) * (high - low). It "interpolates" the position like a human searching a phone book —
looking for "Zhao" you'd jump near the end, not the middle. Time: O(log log n) average for uniform data —
better than O(log n). Worst case: O(n) for non-uniform data. Use when: data is uniformly distributed and
sorted.

Q: How would you search in a 2D sorted matrix?

A: A 2D matrix where rows and columns are both sorted (each row left-to-right, each column
top-to-bottom). Optimal approach: Staircase Search — start at top-right corner. If current == target →
found. If current > target → move left (eliminate this column). If current < target → move down (eliminate
this row). Time: O(m + n) where m=rows, n=columns — much better than O(m*n) brute force. Alternative:
Binary Search on each row → O(m log n). Staircase is better for square matrices. Binary search on rows is
simpler to code.

Tricky & Advanced Questions

Q: What is the best sorting algorithm for nearly sorted data?

A: Insertion Sort is the best for nearly sorted data. If each element is at most k positions from its sorted
position, Insertion Sort runs in O(nk) time. For k=1 (nearly sorted), it's O(n) — linear! Shell Sort also works
well for nearly sorted data. TimSort (Java's sort) takes advantage of existing "runs" of sorted data — this is
why it's O(n) best case for already-sorted arrays.

Sorting & Searching Algorithms — Complete DSA Guide | Page 32

 Q: Can you sort a million integers in less than O(n log n)?

A: Yes! If the integers are bounded in a known range k. Counting Sort: O(n + k). If k is similar to n, this is
O(n) — linear! Radix Sort: O(d*(n+k)) where d = number of digits. For 32-bit integers, d=10 (base 10).
Practically O(n) for fixed-size integers. Bucket Sort: O(n) average if data is uniformly distributed. These are
possible because they don't use comparisons — they exploit the structure of data. The Ω(n log n) lower
bound only applies to comparison-based sorts!

Q: How does Java's [Link]() work for primitive vs object arrays?

A: For PRIMITIVE arrays (int[], double[], etc.): Java uses Dual-Pivot QuickSort. Two pivots partition array
into 3 parts. Average O(n log n), in-place, faster than classic QuickSort. Unstable (but stability doesn't
matter for primitives — all elements are values, not objects). For OBJECT arrays (Integer[], String[],
custom objects): Java uses TimSort. TimSort = Merge Sort + Insertion Sort hybrid. Stable, O(n log n) worst
case, O(n) for sorted data. Stability matters for objects — equal objects should maintain their original
relative order.

Q: What happens if you sort an already-sorted array with Quick Sort?

A: With naive Quick Sort (last element as pivot): worst case O(n²)! On array [1,2,3,4,5], pivot=5, partition
creates: [] and [1,2,3,4]. Next: pivot=4, creates: [] and [1,2,3]. We get n-1 recursive calls, each doing O(n)
work → O(n²). The recursion tree is a straight line (no branching) — n levels deep. Solution: use random
pivot or median-of-three. With random pivot, the probability of this worst case is astronomically small.

Ultimate Quick Reference Cheat Sheet

Algorithm Best Worst Space Stable Use When

Teaching only. Optimise with swapped

Bubble Sort O(n) O(n²) O(1) Stable
flag.

Minimum swaps O(n). Good when

Selection Sort O(n²) O(n²) O(1) Unstable
writes costly.

Best for small/nearly sorted. Used in

Insertion Sort O(n) O(n²) O(1) Stable
TimSort.

Guaranteed. Best for linked lists.

Merge Sort O(n log n) O(n log n) O(n) Stable
External sort.

Sorting & Searching Algorithms — Complete DSA Guide | Page 33

 Algorithm Best Worst Space Stable Use When

Quick Sort O(n log n) O(n²) O(log n) Unstable Fastest in practice. Use random pivot.

Guaranteed + in-place. Good for

Heap Sort O(n log n) O(n log n) O(1) Unstable
limited memory.

Counting Sort O(n+k) O(n+k) O(k) Stable Linear! Only integers in known range.

Radix Sort O(d(n+k)) O(d(n+k)) O(n+k) Stable Linear for fixed-size integers.

Linear Search O(1) O(n) O(1) N/A Any data. Unsorted. Simple.

Binary Search O(1) O(log n) O(1) N/A REQUIRES sorted array. Very fast.

All the Best, Roshan! ■ Algorithms Mastered!

Bubble se Binary Search tak — sab clear hai. Now ace those DSA rounds!

Sorting & Searching Algorithms — Complete DSA Guide | Page 34