Sorting Algorithms

Question 1

Quick Sort Time & Space Complexity

Answer 1

Quick Sort (Divide & Conquer)

• Time Complexity
  
  • Best: O(n log n)
  • AVG: O(n log n)
  • Worst: O(n^2) - when the pivot is always the smallest or largest element
• Space Complexity
  
  • O(log n) - due to the recursion stack

Question 2

Merge Sort Time & Space Complexity

Answer 2

Merge Sort (Divide & Conquer)

• Time Complexity
  
  • Best: O (n log n)
  • AVG: O (n log n)
  • Worst: O (n log n) - same for all cases
• Space Complexity
  
  • O(n) - for temporary arrays used during the merge process

Question 3

Heap Sort Time & Space Complexity

Answer 3

• Time Complexity
  
  • Best: O (n log n)
  • AVG: O (n log n)
  • Worst: O (n log n)
• Space Complexity
  
  • O(n) for heapq (min-heap, push/pop)
  • O (1) (only for manual)

Question 4

When to use Merge Sort

Answer 4

large datasets

when stability is needed (not OK if equal elements are moved around after sorting)

linked lists

Question 5

When not to use merge sort

Answer 5

small datasets (overhead isnt worth it. overhead = processing power, memory)

memory constrained environments

Question 6

Strengths of Merge Sort

Answer 6

Stable sorting (equal objects won’t move around places)

Guaranteed O(n log n) time complexity

good for linked lists

Question 7

weaknesses of merge sort

Answer 7

O(n) space complexity (requires extra memory)

slower than quicksort on average

Question 8

when to use quicksort

Answer 8

small to medium datasets

when average case performance matters

in-place sorting desired (modifies input data directly, spatially efficient)

Question 9

when not to use quicksort

Answer 9

worst-case performance is bad (already sorted data)

when stability is needed (not OK with it moving around values of equal value)

Question 10

strengths of quick sort

Answer 10

average case O(n log n) time

in place sorting: O(log n) space

Question 11

weaknesses of quick sort

Answer 11

worst case O(n^2) time complexity

not stable

recursive depth can lead to stack overflow on large datasets

Question 12

when to use heap sort

Answer 12

when guaranteed O(n log n) performance is needed

memory constrained environments

steaming data (continuous data flow)

Question 13

when not to use heap sort

Answer 13

for small datasets (often slower than other algorithms)

when stability is required (no moving around same value objects)

Question 14

strengths of heapsort

Answer 14

guaranteed O(n log n) time complexity

useful for priority queues

Question 15

weaknesses of heap sort

Answer 15

not stable

slow than quicksort on average

Question 16

explain merge sort

Answer 16

Merge sort breaks the data up into halves over and over until every data point is isolated down like a tree.

Then it rebuilds up by sorting each node of the tree one step at a time

Question 17

explain quick sort

Answer 17

Quick sort uses a recurring pivot splitting the dataset into halves over and over before reassembling the sorted halves

Question 18

explain heap sort

Answer 18

Heap (max heap) method involves creating a heap version of the array.

It extracts the root (max value in the heap) and replaces it with the last element of the real array.

Question 19

Timsort

Answer 19

used in Python’s built in sort() and sorted() functions. It’s a hybrid sorting algorithm that combines merge sort and insertion sort. Can handle semi sorted and unsorted data.

Question 20

Is Timesort stable?

Answer 20

Timsort is a stable sort, meaning it preserves the relative order of equal elements

Question 21

Difference between sort() and sorted()

Answer 21

Sort is a method that’s used on lists (modifies the original list in place)

Sorted is a method that can be used on any iterable object (tuples, lists, strings, etc). It creates a new sorted list without modifying the OG iterable.

Question 22

Time complexity of Timsort

Answer 22

Best: O(n) - when already sorted (timsort detects this)
AVG Case: O(n log n) - timsort behaves like merge sort
Worst Case: O(n log n)

Question 23

Space complexity of Timsort

Answer 23

O(n) - requires space for temporary storage during merging phase

    - Sorted () is actually O(2n) but it’s O(n) in space complexity representation. Sorted uses more space than Sort( ) as it creates a new object.