Algorithm - Sorting

updated in crl

Sorting Algorithms

Time and Space Complexity

Basic Sort :

Sorting Algorithm	Worst Time Complexity	Average Time Complexity	Best Time Complexity	Space Complexity
Selection Sort	O(n^2)	O(n^2)	O(n^2)	O(1)
Bubble Sort	O(n^2)	O(n^2)	O(n) ⭐ (with swap-flag optimization)	O(1)
Insertion Sort	O(n^2)	O(n^2)	O(n) ⭐ (already sorted)	O(1)
Quick Sort	O(n^2) ⭐	O(n * log n)	O(n * log n)	O(log n) (avg recursion) / O(n) (worst recursion) ⭐
Merge Sort	O(n * log n)	O(n * log n)	O(n * log n)	O(n)
Heap Sort ⭐	O(n * log n)	O(n * log n)	O(n * log n)	O(1) ⭐(aux space)

Advance Sort :

Sorting Algorithm	Best Time Complexity	Average Time Complexity	Worst Time Complexity	Space Complexity
Shell Sort	O(n * log n)	O(n * log^2 n)	O(n^2)	O(1)
Counting Sort	O(n + k)	O(n + k)	O(n + k)	O(k)
Radix Sort ⭐	O(nk)	O(nk)	O(nk)	O(n + k)
Bucket Sort	O(n + k)	O(n + k)	O(n^2)	O(n + k)
Tim Sort	O(n)	O(n * log n)	O(n * log n)	O(n)

Comparison Sort and Alternatives

Fastest Sort : Quick Sort ->Average TC:O(n*logn)

Comparison Sorting

• Quicksort usually has a running time of n x log(n), but is there an algorithm that can sort even faster? In general, this is not possible. Most sorting algorithms are comparison sorts, i.e. they sort a list just by comparing the elements to one another. A comparison sort algorithm cannot beat n x log(n) (worst-case) running time, since n x log(n) represents the minimum number of comparisons needed to know where to place each element. For more details, you can see these notes (PDF).

Alternative Sorting

• Another sorting method, the counting sort, does not require comparison. Instead, you create an integer array whose index range covers the entire range of values in your array to sort. Each time a value occurs in the original array, you increment the counter at that index. At the end, run through your counting array, printing the value of each non-zero valued index that number of times.

Properties of Sorting

Algorithm	Stable	In-Place	Adaptive	Internal	Online
Selection Sort	❌	✅	❌	✅	❌
Bubble Sort	✅	✅	✅	✅	❌
Insertion Sort	✅	✅	✅	✅	✅
Quick Sort	❌	✅	❌	✅	❌
Merge Sort	✅	❌	❌	✅	❌
Heap Sort	❌	✅	❌	✅	✅
Shell Sort	❌	✅	❌	✅	❌
Counting Sort	✅	❌	❌	✅	❌
Radix Sort	✅	❌	❌	✅	❌
Bucket Sort	✅	❌	❌	✅	❌
Tim Sort	✅	❌	✅	✅	❌

All Sorts are Internal Sorts, While Merge sort is both Internal and External.

Comparison-based vs Non Comparison-based

Property	Meaning	Examples
Comparison-based	Uses comparisons	Selection Sort, Bubble Sort, Insertion Sort, Quick Sort, Merge Sort, Heap Sort, Shell Sort, Tim Sort
Non-comparison-based	Uses counting/bucketing	Counting Sort, Radix Sort, Bucket Sort

Key Point:- Shell Sort & Tim Sort advance sorting are also Comparison based

1. Stable vs Unstable ⭐

Property	Meaning	Examples
Stable	Preserves order of equal elements	Bubble Sort, Insertion Sort, Merge Sort, Counting Sort, Radix Sort, Tim Sort, Bucket Sort
Unstable	May change order of equal elements	Selection Sort, Quick Sort, Heap Sort, Shell Sort

Key Point:- Selection Sort, Quick Sort & Heap Sort are not Stable

2. In-Place vs Not In-Place ⭐

Property	Meaning	Examples
In-place	Uses O(1) extra space	Selection Sort, Bubble Sort, Insertion Sort, Quick Sort, Heap Sort, Shell Sort
Not In-place	Uses extra memory	Merge Sort, Counting Sort, Radix Sort, Bucket Sort, Tim Sort

Key Point: - Merge Sort is Not In-Place

3. Adaptive vs Non-adaptive ⭐

Property	Meaning	Examples
Adaptive	Faster on nearly sorted data	Insertion Sort, Bubble Sort , Tim Sort
Non-adaptive	Ignores existing order	Selection Sort, Quick Sort, Merge Sort, Heap Sort, Shell Sort, Counting Sort, Radix Sort, Bucket Sort

Key Point:- Only Insertion Sort, Bubble Sort & Tim Sort are Adaptive

4. Internal vs External ⭐

Property	Meaning	Examples
Internal	Data fits in RAM	All Sort
External	Data stored on disk	External Merge Sort

Key Point:- Only Merge Sort is External Sort. It have both Internal and External Sort version

5. Online vs Offline

Property	Meaning	Examples
Online	Input arrives gradually	Insertion Sort, Heap Sort
Offline	Needs complete input first	Selection Sort, Bubble Sort, Quick Sort, Merge Sort, Heap Sort*, Shell Sort, Counting Sort, Radix Sort, Bucket Sort, Tim Sort

Key Point:- Only Insertion Sort & Heap Sort is Online

6. Deterministic vs Randomized

Property	Meaning	Examples
Deterministic	Same behavior always	Selection Sort, Bubble Sort, Insertion Sort, Merge Sort, Heap Sort, Shell Sort, Counting Sort, Radix Sort, Bucket Sort, Tim Sort
Randomized	Uses randomness	Randomized Quick Sort

Key Point:- All Sorts are Deterministic Except, Randomized Quick Sort

Summary

Term	Definition	Why it matters
Stable	If two elements compare equal, their original relative order is preserved after sorting.	Important when a list has secondary keys (e.g., sort by last name then keep the existing first-name order).
In-place	The algorithm uses only O(1) (or a very small constant) extra memory beyond the input array itself.	Saves RAM – crucial for huge data sets or memory-constrained environments.
Adaptive	The running time improves when the input is already partially ordered. Typically the cost is O(n + f(disorder)) where disorder measures how far the list is from sorted (e.g., number of inversions).	Gives near-linear performance on “almost-sorted” data, which occurs a lot in real programs (log files, UI tables, etc.).
Internal	The entire data set fits in the main memory (RAM) during sorting.	Faster because accessing RAM is much quicker than accessing secondary storage. Most classical sorting algorithms are internal sorts.
Online	The algorithm can process elements one by one as they arrive; it does not require the complete input beforehand.	Useful for streams of data, real-time systems, and continuously growing datasets.

Stable, In-Place, Adaptive, Internal and Online

Sort Algorithms that satisfy all three (Stable, In-Place & Adaptive) properties :

Algorithm	Reason it meets all three
Insertion Sort	Stable by nature, works in‑place on the original array, and stops early when the input is already (or nearly) sorted (O(n) best).
Bubble Sort	Each pass swaps only adjacent out‑of‑order pairs → stable; uses only a few extra variables → in‑place; terminates when a full pass makes no swap → adaptive.
Binary Insertion Sort (stable implementation)	Same as insertion sort, just finds the insertion point with binary search – still stable, in‑place, and adaptive.

Practical tip: For real‑world code you rarely use plain bubble sort because its constant factors are high. Insertion sort is excellent for small or nearly sorted sub‑arrays (e.g., as the “insertion‑sort fallback” inside TimSort or introsort). If you need a stable, adaptive algorithm on large data and can afford linear extra memory, TimSort is usually the best choice.

Sorting algorithms classified by these properties :

Algorithm	Stable?	In‑place?	Adaptive?	Typical time complexity*
Insertion Sort	✅	✅	✅ (runs in O(n + inv); inv = #inversions)	O(n²) worst, O(n) best
Bubble Sort	✅	✅	✅ (stops early when no swaps)	O(n²) worst, O(n) best
Binary Insertion Sort	✅ (if insertion is stable)	✅	✅ (same adaptivity as plain insertion)	Same as insertion
Shell Sort	❌ (standard version)	✅	✅ (faster on partially sorted data)	≈ O(n log² n) depending on gap sequence
TimSort (Python’s/Java’s built‑in sort for objects)	✅	⚠️ Not strictly in‑place – uses a temporary run buffer of size ≤ n/2 (often O(n) worst case)	✅ (detects runs, merges them)	O(n log n) worst, O(n) best on already sorted
Merge Sort (classic top‑down)	✅	❌ (O(n) extra array)	❌ (does not gain from presorted input)	O(n log n) always
Bottom‑up Merge Sort with in‑place merging	✅ (possible)	⚠️ In‑place variants exist but are complex and slower	❌ (still O(n log n))	O(n log n)
QuickSort (Lomuto/Hoare partition)	❌ (standard)	✅	❌ (doesn’t adapt to order)	O(n log n) avg, O(n²) worst
Random‑pivot QuickSort	❌	✅	❌	Same as QuickSort
Stable QuickSort (extra buffer or linked list)	✅ (with extra memory)	❌ (needs O(n) aux)	❌	O(n log n)
HeapSort	❌	✅	❌	O(n log n) always
Selection Sort	✅ (if you keep equal‑key order when swapping) but usually implemented unstable	✅	❌ (always scans whole unsorted part)	O(n²)
Counting Sort / Radix Sort	✅	⚠️ Not in‑place – needs counting array or buckets (O(k) extra)	✅ (linear on already sorted keys)	O(n + k)
Bucket Sort	✅ (if buckets keep order)	⚠️ Not strictly in‑place (needs bucket storage)	✅ (fast when data already clustered)	O(n + k)

1. Stable vs Unstable Sort

Stable Sorting: If two elements have the same key (equal value), their relative order in the original array is preserved in the sorted output.

Unstable Sorting: If two equal elements may change their relative order after sorting.

Example:
Array = [4a, 3, 4b, 2] (4a and 4b are equal but distinct items)

• Stable sort result: [2, 3, 4a, 4b] (order of 4a before 4b is preserved)
• Unstable sort result: [2, 3, 4b, 4a] (order of equal elements changed)

Stable Sorting Algorithms

• Bubble Sort → ✅ Stable → Swaps only adjacent elements, so equal elements never cross order.
• Insertion Sort → ✅ Stable → Inserts element into sorted part without jumping equal elements ahead.
• Merge Sort → ✅ Stable → During merge, if equal, it takes the left one first (preserves original order).
• Counting Sort → ✅ Stable → Places elements in output array in order of input traversal.
• Radix Sort → ✅ Stable → Relies on Counting Sort as subroutine, which is stable.
• Bucket Sort → ✅ Stable (if stable sub-sort like Insertion is used inside buckets).
• TimSort → ✅ Stable → Designed to be stable (merge + insertion hybrid).
• Cocktail Shaker Sort → ✅ Stable → Bidirectional Bubble Sort, still only adjacent swaps.
• Odd-Even Sort → ✅ Stable → Adjacent comparisons like Bubble, order preserved.
• C++ stable_sort → ✅ Stable → Explicitly implemented to keep equal order (uses Merge-like logic).

Unstable Sorting Algorithms

• Selection Sort → ❌ Unstable → Swaps non-adjacent elements; equal elements can jump over each other.
• Quick Sort → ❌ Unstable → Partition step may reorder equal elements around pivot.
• Heap Sort → ❌ Unstable → Heapify swaps elements far apart, disturbing order of equals.
• Shell Sort → ❌ Unstable → Elements are moved across large gaps, breaking order of equals.
• IntroSort (STL sort) → ❌ Unstable → Based on Quick + Heap + Insertion, instability inherited.
• Tournament Sort → ❌ Unstable → Equal elements may be promoted/replaced in tree arbitrarily.

👉 Shortcut to remember:

• Most O(n²) simple sorts: Bubble (stable), Insertion (stable), Selection (unstable).
• Most O(n log n) divide & conquer sorts: Merge (stable), Quick (unstable), Heap (unstable).
• Counting/Radix/Bucket → stable, because they don’t rely only on comparisons.

👉 Shortcut Rule:

• Algorithms that only swap neighbors (Bubble, Insertion, Odd-Even) → Stable.
• Algorithms that move elements far apart (Selection, Quick, Heap, Shell) → Unstable.

2. In-place vs Out-of-place Sorting

In-place Sorting Algorithms (Use only constant or O(1) extra space, besides recursion stack)

• Bubble Sort → In-place
• Insertion Sort → In-place
• Selection Sort → In-place
• Quick Sort → In-place (needs recursion stack O(log n))
• Heap Sort → In-place
• Shell Sort → In-place
• IntroSort (C++ STL sort) → In-place

Out-of-place Sorting Algorithms (Require extra arrays or large auxiliary space, $O(n)$ or more)

• Merge Sort → Out-of-place (needs $O(n)$ auxiliary array)
• Counting Sort → Out-of-place (needs $O(n+k)$ array)
• Radix Sort → Out-of-place (needs counting arrays + temporary storage)
• Bucket Sort → Out-of-place (needs buckets)
• TimSort → Out-of-place (needs temporary arrays)
• External Merge Sort → Out-of-place (disk-based, very large data)

Ques. Why Quick Sort is In-Place if it take O(logn) space complexity

• In-place sorting means: the algorithm does not need extra arrays proportional to n, it mostly rearranges elements in the same array. Quick Sort only uses extra space for the recursion stack, which is O(log n) on average. This log n stack space is tiny compared to creating a full extra array of size n, so it’s still considered in-pla

👉 Shortcut rule:

• Simple “swap-based” sorts (Bubble, Insertion, Selection, Quick, Heap, Shell) → In-place
• “Auxiliary-array based” sorts (Merge, Counting, Radix, Bucket, TimSort) → Out-of-place

---

Question & Answers

Important QA Concept

---

Questions & Answers

Easy Sorting Q/A

1. Fastest average-case sorting? Quick Sort
2. Guaranteed O(n log n) sorting? Merge Sort
3. Sorting for linked list? Merge Sort
4. Sorting for priority queue?
   Heap Sort
5. Non-comparison-based sorting? Counting, Radix, Bucket
6. Which sort is best for small arrays?
   Insertion Sort; Time: $O(n^2)$, Space: $O(1)$.
7. Which sorting algorithm is stable and has $O(n \log n)$ worst-case time?
   Merge Sort; Time: $O(n \log n)$, Stable.
8. Which algorithm is used for heap-based priority queues?
   Heap Sort; Time: $O(n \log n)$, Space: $O(1)$
9. Which sorting is fastest in average case?
   Quick Sort; Time: $(n \log n)$ average, Space: $O(\log n)$.
10. Which algorithm is guaranteed stable and out-of-place?
    Merge Sort; Space: $O(n)$
11. Which sort is in-place but unstable?
    Heap Sort; Space: O(1), Unstable.
12. Which sort is good for linked lists?
    Merge Sort.
13. Which sorting is non-comparison based?
    Counting Sort; Time: $O(n + k)$
14. Which sort works using digit grouping?
    Radix Sort; Time: $O(dn)$, where $d$ is digits.
15. Which algorithm is used by Python’s built-in sort? ⭐⭐⭐ Timsort (Hybrid of Merge and Insertion Sort).
16. Which sort is unstable but in-place?
    Quick Sort; Space: $O(log n)$.
17. Which sort is stable and in-place for small arrays?
    Insertion Sort.
18. Which sort swaps minimum element to correct place each time?
    =Selection Sort=; Time: $O(n^2)$, Space: $O(1)$.
19. Which sort is best for nearly sorted data?
    Insertion Sort; Time: $O(n)$ best case.
20. Which sorting is divide and conquer + merging?
    Merge Sort.
21. Which sorting algorithm uses a pivot for partitioning?
    Quick Sort.
22. What is the worst-case time complexity of Bubble Sort?
    Time: $O(n^2)$
23. Which sort is both adaptive and stable?
    Insertion Sort.
24. Which sort requires range information for $O(n)$ time?
    Counting Sort.
25. Which sort is slow but simple for small data?
    Bubble Sort; Time: $O(n^2$).
26. Which sort uses heap data structure?
    Heap Sort; Space: $O(1)$.
27. Which sort is good for external sorting (large files)?
    Merge Sort; Space: $O(n)$.
28. Which sort is not stable by default?
    Heap Sort; Unstable.
29. Which sort requires extra space for merging?
    Merge Sort; Space: $O(n)$.
30. Which sort is best for large unsorted arrays?
    Quick Sort; Time: $O(n\log⁡n)$ average case.
31. Which sort is used in Java for primitives? ⭐⭐⭐ Dual-Pivot Quick Sort.
32. Which sorting uses minimum assignment operations?
    Selection Sort. ⭐
33. Which sort can detect sorted input to finish early?
    Bubble Sort (with optimization).
34. Which sort is good for repeated keys?
    Counting Sort. ⭐
35. Which sort is bad for large datasets?
    Bubble Sort; Time: $O(n^2)$. ❓
36. Which sort is both non-adaptive and unstable?
    Selection Sort.
37. Which sort merges two sorted lists efficiently?
    Merge Sort.
38. Which sort’s worst case is when data is sorted?
    Quick Sort (with poor pivot).
39. Which sort uses a heap for sorting in-place?
    Heap Sort.
40. Which sort is used in STL C++ sort()? ⭐⭐⭐ IntroSort (Hybrid).
41. Which sort compares every adjacent pair repeatedly?
    Bubble Sort.
42. Which sort fills sorted position in every pass?
    Selection Sort.
43. Which sort is highly parallelizable?
    Merge Sort. ⭐
44. Which sort’s best case and worst case is same?
    Selection Sort; Time: $O(n^2)$. ❓
45. Which sort partitions around a pivot?
    Quick Sort.
46. Which sort is stable and works well for small files?
    Insertion Sort.
47. Which sort is not in-place?
    Merge Sort; Space: $O(n)$.
48. Which sort is in-place and simple to implement?
    Insertion Sort. ❓
49. Which sort divides array until one element subarrays?
    Merge Sort.
50. Which sort prefers swap over comparison cost?
    Selection Sort. ⭐
51. Which sort is fastest for random large arrays?
    Quick Sort (on average).
52. Which sort’s basic operation is bubble-up or bubble-down?
    Heap Sort. ⭐
53. Which sort’s performance unaffected by input order?
    Merge Sort. ⭐
54. Which sort is unstable unless modified for stability?
    Quick Sort. ⭐
55. Which sort is optimal for sorting strings or digits?
    Radix Sort; Time: $O(nd)$.

Medium Sorting Questions and Answers

1. How is stability achieved in Merge Sort?
   Merge carefully reorders equal elements during merging; Time: O(nlog⁡n)O(n \log n)O(nlogn), Stable.
2. What is the space complexity of Heap Sort?
   Space: O(1)O(1)O(1), In-place and Unstable.
3. How does Quick Sort pick pivots to avoid worst-case?
   Median-of-three or randomized selection makes partitions more balanced; Time: O(nlog⁡n)O(n \log n)O(nlogn) average.
4. How is time complexity of Counting Sort determined?
   Time: O(n+k)O(n + k)O(n+k), where kkk is the range of keys.
5. Why might Radix Sort be preferred over Merge Sort?
   Faster than comparison-based sorts when input is digit-based and range not too wide; Time: O(nd)O(n d)O(nd).
6. How does IntroSort combine three sorts?
   Uses Quick Sort, switches to Heap Sort if recursion too deep; ends with Insertion Sort for small arrays; Time: O(nlog⁡n)O(n \log n)O(nlogn).
7. Which sorting is ideal for streaming data insertion?
   Insertion Sort adapts quickly; Time: O(n2)O(n^2)O(n2) worst; O(n)O(n)O(n) best.
8. Which sort is non-adaptive but stable?
   Merge Sort; always O(nlog⁡n)O(n \log n)O(nlogn).
9. What are the steps in Bucket Sort?
   Divide input into buckets, sort each bucket (typically Insertion Sort); Time: depends on distribution, average O(n)O(n)O(n).
10. Best sorting for external (disk) sorting?
    Merge Sort handles large files; Space: O(n)O(n)O(n).
11. Why is heapify used in Heap Sort?
    To maintain heap property after each removal; Time: O(n)O(n)O(n) for building heap, then O(nlog⁡n)O(n \log n)O(nlogn).
12. Which algorithm is sensitive to repeated elements?
    Quick Sort can degrade with many duplicates; 3-way partitioning can help.
13. Which algorithm offers best parallelization?
    Merge Sort easily subdivides tasks; Time: O(nlog⁡n)O(n \log n)O(nlogn).
14. Time complexity for Selection Sort on partially sorted data?
    Always O(n2)O(n^2)O(n2), not adaptive.
15. Space requirement for Counting Sort?
    O(k)O(k)O(k) for counts, O(n)O(n)O(n) for output.
16. Sorting algorithm for large, nearly sorted datasets?
    Timsort; combines insertion and merge; Time: O(n)O(n)O(n) best, O(nlog⁡n)O(n \log n)O(nlogn) worst.
17. What is the best-case complexity for Bubble Sort?
    O(n)O(n)O(n) if array already sorted.
18. What is a stable variant of Quick Sort?
    Implementing with additional arrays; not in-place, but stable.
19. Which sorting uses recursion stack space?
    Quick Sort and Merge Sort; Space: O(log⁡n)O(\log n)O(logn).
20. Why is Selection Sort poor for adaptive cases?
    Does not exploit existing order; always quadratic time.
21. Best algorithm for finding the Kth smallest element?
    QuickSelect (based on Quick Sort); Time: O(n)O(n)O(n) average.
22. What algorithm sorts by repeatedly extracting min/max?
    Selection Sort or Heap Sort (using heap property).
23. Which sorting is used in C++ STL for large inputs?
    IntroSort switches between Quick, Heap, Insertion; Time: O(nlog⁡n)O(n \log n)O(nlogn).
24. How is stability defined in sorting algorithms?
    Equal keys retain their relative order; Merge, Bubble, Insertion are stable.
25. Which sorting algorithm is not stable and not adaptive?
    Heap Sort.
26. What is the maximum recursion depth in Quick Sort?
    Up to O(n)O(n)O(n) worst-case (stack overflow risk), typically O(log⁡n)O(\log n)O(logn).
27. Which sorting uses divide and conquer for arrays?
    Merge Sort and Quick Sort.
28. Best sorting for only distinct keys and bounded range?
    Counting Sort; Time: O(n+k)O(n + k)O(n+k).
29. Which sort is slow when input range is huge?
    Counting Sort uses too much space for large kkk.
30. Which sort can be optimized for cache locality?
    Quick Sort (partitioning on contiguous memory).
31. How does merge operation work in Merge Sort?
    Combines two sorted arrays in O(n)O(n)O(n).
32. How can Quick Sort be made stable?
    By using extra space; result is not in-place.
33. Best algorithm to sort constant-range integers?
    Counting Sort; Time: O(n)O(n)O(n).
34. How does heapify-up differ from heapify-down?
    Heapify-up for insertion, heapify-down for removal in Heap Sort.
35. Which sorting algorithm is used in Java for objects?
    Timsort; stable; Time: O(nlog⁡n)O(n \log n)O(nlogn).
36. Best way to merge sorted linked lists?
    Merge Sort or iterative merging; Time: O(n)O(n)O(n).
37. What is the overhead for Merge Sort in space?
    At least O(n)O(n)O(n) extra memory requirement.
38. Which sorting minimizes the number of data writes?
    Selection Sort; fewest swaps per pass.
39. Which algorithm sorts based on character strings efficiently?
    Radix Sort (with fixed or bounded length strings); Time: O(nk)O(nk)O(nk).github
40. How can sorting help solve three sum problems?
    Sort the array then use two pointers for combination search.
41. Algorithm to reorder log files: Letters before digits?
    Custom stable sort (Timsort or Merge Sort preferred).
42. Which sort works well on uniform distribution?
    Bucket Sort; Time: O(n)O(n)O(n) average case.
43. Algorithm that minimizes comparisons in best case?
    Insertion Sort; Time: O(n)O(n)O(n) if nearly sorted.
44. How does multi-way merge extend Merge Sort?
    Merges kkk sorted arrays instead of two; Time: O(nlog⁡k)O(n \log k)O(nlogk).
45. Time complexity of Timsort for random data?
    O(nlog⁡n)O(n \log n)O(nlogn).
46. Which sort is highly cache unfriendly?
    Classic Merge Sort.
47. Mitigation for Quick Sort stack overflows?
    Use tail recursion or iterative approach.
48. Best approach for finding duplicates with sorting?
    Sort array, scan for adjacent duplicates (any O(nlog⁡n)O(n \log n)O(nlogn) sort).
49. How does natural Merge Sort differ from classic?
    Detects pre-existing runs and merges bigger blocks; Time: depends on order.
50. Which sort is used in Unix’s sort utility?
    Usually Merge Sort or Timsort for stability on large files.

Hard Sorting Questions and Answers

1. How do you make any unstable sort stable?
   By pairing data with original indices and using these as tie-breakers; increases space to O(n)O(n)O(n).interviewkickstart
2. How to sort a huge dataset not fitting in RAM?
   Use External Merge Sort; Time: O(nlog⁡n)O(n \log n)O(nlogn) I/O, divides into chunks, sorts in-memory, merges.finalroundai
3. When does Quick Sort’s recursion stack overflow?
   Worst-case: O(n)O(n)O(n) recursion depth if poor pivots; avoid by median-of-three/randomized partitioning.finalroundai
4. How do you make Quick Sort stable?
   Use extra arrays to partition, losing in-place advantage.finalroundai
5. Explain in-place merge for Merge Sort.
   Achievable but increases time to O(nlog⁡2n)O(n \log^2 n)O(nlog2n); typical merge sort uses O(n)O(n)O(n) extra space for merging.geeksforgeeks
6. Can you reverse a string array lexicographically in O(n)?
   No, comparison-based sorts require O(nlog⁡n)O(n \log n)O(nlogn); but use Counting/Radix Sort if bounds known.geeksforgeeks
7. How does Timsort detect natural runs?
   Finds ascending/descending runs, merges with size thresholds; Time: O(n)O(n)O(n) best, O(nlog⁡n)O(n \log n)O(nlogn) worst.geeksforgeeks
8. How to optimize Quick Sort on many duplicates?
   Use 3-way partitioning (“Dutch National Flag”); reduces redundant pivots.geeksforgeeks
9. Explain stable Bucket Sort for floating-point numbers.
   Place values into O(n)O(n)O(n) buckets, stable sort each with list or queue; average O(n)O(n)O(n) if uniformly distributed.geeksforgeeks
10. What’s the lower bound for comparison-based sorting?
    Ω(nlog⁡n)\Omega(n \log n)Ω(nlogn) for any deterministic comparision-based algorithm.interviewkickstart
11. Is Heap Sort stable or unstable? Why?
    Heap Sort is unstable due to element swaps not preserving equal keys’ order.interviewkickstart
12. Which sort is best for very large distributed merge?
    Multi-Way Merge Sort, where kkk-way merge optimizes merge cost in O(nlog⁡k)O(n \log k)O(nlogk).finalroundai
13. What’s the cache complexity of Merge Sort?
    Poor in naive version, better as Merge Path or Tiled Merge Sort; shifting blocks improves locality.geeksforgeeks
14. Counting Sort: when optimal? When catastrophic?
    Optimal when k=O(n)k = O(n)k=O(n); impractical if k≫nk \gg nk≫n, e.g. massive integer range.finalroundai
15. When can Radix Sort outperform Merge/Quick?
    If word size/bounded digits, Time: O(nd)O(nd)O(nd) with counting sort as stable sub-routine.techinterviewhandbook
16. Can Shell Sort reach O(nlog⁡n)O(n \log n)O(nlogn) time?
    Yes, with specific gap sequences (e.g., Pratt sequence), but tricky; usually O(n3/2)O(n^{3/2})O(n3/2).techinterviewhandbook
17. How does Bitonic Sort work?
    Recursively builds bitonic sequences, then merges; Time: O(log⁡2n)O(\log^2 n)O(log2n) depth (parallel).techinterviewhandbook
18. Why can’t Heap Sort be perfectly parallelized?
    Heapify and extract-min steps are serial, merge and distribution are easier to parallelize.geeksforgeeks
19. Which sort achieves best-case O(n)?
    Insertion Sort, Counting Sort, and Timsort for nearly sorted inputs.geeksforgeeks
20. How to minimize write operations in sorting?
    Cycle Sort and Selection Sort minimize data writes; Cycle Sort does exactly n writes for unique entries.interviewkickstart
21. Explain Adaptive Heap Sort.
    Modifies heap structure based on run length; more efficient if input is partially sorted.techinterviewhandbook
22. Where is Odd-Even Sort applicable?
    Suitable for parallel hardware (sorting networks); Time: O(n2)O(n^2)O(n2) sequential, optimal on some hardware.techinterviewhandbook
23. How does Flashsort achieve linear time?
    Maps items to buckets via proportion, then sorts each; ideal for uniform distributions; average O(n)O(n)O(n).interviewkickstart
24. When can you reduce Merge Sort space to O(1)?
    Using in-place merge (Reinhardt’s algorithm), but at a cost of increased time complexity; rarely practical.geeksforgeeks
25. Tail recursion optimization for Quick Sort?
    Always recurse to the smaller subarray; converts other call to a loop, reduces stack.finalroundai
26. Define a stable, in-place, O(n\log n) sort.
    Classic Merge Sort is not in-place, but binary insertion sort can be in-place and stable on bounded data.interviewkickstart
27. How to efficiently merge K sorted arrays?
    Use a min-heap; Time: O(nlog⁡k)O(n \log k)O(nlogk) where nnn is total elements.finalroundai
28. When is Timsort worst-case O(n log n)?
    Adversarial data that defeats natural run detection; still never slower than O(n log n).geeksforgeeks
29. Can radix sort work on negatives?
    Yes, with sign bucket separation or digit biasing; total time O(nd)O(nd)O(nd).interviewkickstart
30. Best way to sort massive logs by timestamp?
    External Merge Sort, chunk and merge approach, O(n log n) disk I/O.finalroundai
31. How does patience sorting relate to LIS?
    Builds piles for LIS, uses binary search for O(nlog⁡n)O(n \log n)O(nlogn) LIS computation.interviewkickstart
32. How to ensure stability in multi-key sort (lex sort)?
    Sort on least-significant key first, repeat for all keys (radix principle).techinterviewhandbook
33. What’s the sorting complexity for read-only arrays?
    Minimum is O(n2)O(n^2)O(n2) if extra memory is forbidden (Selection Sort).techinterviewhandbook
34. Which sort is best for sorting objects by multiple fields?
    Stable sort (Merge/Timsort) from least- to most-significant key.interviewkickstart
35. Explain External Natural Merge Sort.
    Scans for runs already present in memory/file, reduces number of merge passes.geeksforgeeks
36. Sorting algorithm with best cache-oblivious properties?
    Cache-Oblivious Merge Sort uses divide and conquer on sub-blocks, optimizes for multiple cache levels.geeksforgeeks
37. How to parallelize sorting on GPU?
    Use bitonic sort or radix sort, both can be parallelized for SIMD/GPU.techinterviewhandbook
38. Space complexity of Counting Sort for Unicode or wide int?
    Can explode to O(k) where k is huge (like Unicode codepoints), making it impractical.finalroundai
39. How is cycle detection used in Cycle Sort?
    Detects where each value belongs and cycles it directly; achieves minimal data writes O(n).interviewkickstart
40. Which sort works for immutable data (read-only)?
    Selection Sort (can sort with only swaps, no duplicates allowed); Time: O(n2)O(n^2)O(n2).techinterviewhandbook
41. Best algorithm for small but frequent sorts?
    Insertion Sort (overhead is tiny, performs optimally for n ≤\leq≤ 20).devinterview
42. Why is block sort “block stable”?
    Block sort (Block Merge Sort, GrailSort) merges using buffer, achieves in-place stable O(nlog⁡n)O(n \log n)O(nlogn).interviewkickstart
43. How is entropy used in sorting lower bounds?
    Comparison tree needs log⁡2(n!)\log_2(n!)log2(n!), justifying comparison sort lower bound; about nlog⁡nn\log nnlogn.interviewkickstart
44. Explain Recursive Insertion Sort and its utility.
    Solves by sorting first n-1 elements recursively, then inserting last; pedagogical, not practical for large n.techinterviewhandbook
45. Which sort optimally sorts linked lists in O(n log n) time?
    Merge Sort, as linked lists lack random access.interviewkickstart
46. Best method to keep an ordered list after many inserts/deletes?
    Self-balancing BST or skip list, not sorting per se, but maintains order in O(log⁡n)O(\log n)O(logn).finalroundai
47. Which sort is used in “k-way” external file sort?
    Multi-way Merge Sort; merges k files at a time for efficient I/O.geeksforgeeks
48. Explain smoothsort’s advantage over heapsort.
    Smoothsort adapts to pre-existing order, can be O(n)O(n)O(n) if nearly sorted, O(nlog⁡n)O(n \log n)O(nlogn) worst-case.finalroundai
49. Find the median in an unsorted array fast.
    Use QuickSelect (Hoare’s selection); expected time: O(n)O(n)O(n).finalroundai
50. Does a comparison-based sort exist with O(n) time?
    No, but non-comparison sorts do for certain constraints (Counting/Radix/Bucket sort).interviewkickstart