📈 Classic Sorting Algorithms

[tpemeja]

Summary

• Patterns

  • Quick Sort: average O(n log n), worst O(n^2); in-place; not stable; randomized pivot to avoid bad cases.
  • Merge Sort: O(n log n); stable; not in-place (O(n) extra); great for linked lists.
  • Heap Sort: O(n log n); in-place (array-based); not stable; good worst-case guarantees.
  • Insertion Sort: O(n^2) worst, O(n) on nearly-sorted; in-place; stable; tiny arrays.
  • Selection Sort: O(n^2); in-place; not stable; minimal swaps.
  • Shell Sort: ~O(n^(3/2)) typical (depends on gaps); in-place; not stable.

• Choose

  • General-purpose with libraries → Python’s built-in sort (Timsort, stable)
  • Teaching/implementing divide-and-conquer → Merge Sort or Quick Sort
  • Guaranteed O(n log n) without extra memory → Heap Sort (array-based)
  • Nearly-sorted or very small n → Insertion Sort
  • Memory-constrained and simple → Selection/Shell Sort (trade-offs apply)

Details

✅ Classic algorithms (arrays)

Summary (Key points):

• Prefer Python’s built-in Timsort for production code.
• The following implementations are educational references in pure Python.

Details

• Case 1: Quick Sort — Sort an Array

  • Average O(n log n), worst O(n^2). Randomized pivot + smaller-first recursion limits stack depth.

  import random
  
  def quicksort(a):
      def partition(l, r):
          p = random.randint(l, r)
          a[r], a[p] = a[p], a[r]
          pivot = a[r]
          i = l
          for j in range(l, r):
              if a[j] < pivot:
                  a[i], a[j] = a[j], a[i]
                  i += 1
          a[i], a[r] = a[r], a[i]
          return i
  
      def sort(l, r):
          while l < r:
              m = partition(l, r)
              # Recurse on smaller side first (limits recursion depth)
              if m - 1 - l < r - (m + 1):
                  sort(l, m - 1)
                  l = m + 1
              else:
                  sort(m + 1, r)
                  r = m - 1
  
      if a:
          sort(0, len(a) - 1)
      return a

• Case 2: Merge Sort — Sort List

  • Stable, O(n log n), O(n) extra space on arrays.

  def mergesort(a):
      n = len(a)
      if n <= 1:
          return a[:]
      mid = n // 2
      left = mergesort(a[:mid])
      right = mergesort(a[mid:])
      i = j = 0
      out = []
      while i < len(left) and j < len(right):
          if left[i] <= right[j]:
              out.append(left[i]); i += 1
          else:
              out.append(right[j]); j += 1
      out.extend(left[i:])
      out.extend(right[j:])
      return out

• Case 3: Heap Sort — Kth Largest Element in an Array

  • In-place variant shown (no heapq); O(n log n), not stable.

  def heapsort(a):
      n = len(a)
  
      def sift_down(i, end):
          while True:
              l = 2 * i + 1
              r = l + 1
              largest = i
              if l < end and a[l] > a[largest]:
                  largest = l
              if r < end and a[r] > a[largest]:
                  largest = r
              if largest == i:
                  break
              a[i], a[largest] = a[largest], a[i]
              i = largest
  
      # Build max-heap
      for i in range(n // 2 - 1, -1, -1):
          sift_down(i, n)
      # Extract
      for end in range(n - 1, 0, -1):
          a[0], a[end] = a[end], a[0]
          sift_down(0, end)
      return a

• Case 4: Insertion Sort — Insertion Sort List

  • O(n^2) worst; great for small or nearly-sorted arrays; stable.

  def insertion_sort(a):
      a = a[:]  # keep input intact
      for i in range(1, len(a)):
          x = a[i]
          j = i - 1
          while j >= 0 and a[j] > x:
              a[j + 1] = a[j]
              j -= 1
          a[j + 1] = x
      return a

• Case 5: Selection Sort

  • O(n^2); minimal swaps; not stable.

  def selection_sort(a):
      a = a[:]
      n = len(a)
      for i in range(n):
          m = i
          for j in range(i + 1, n):
              if a[j] < a[m]:
                  m = j
          a[i], a[m] = a[m], a[i]
      return a

• Case 6: Shell Sort

  • In-place; performance depends on gap sequence; not stable.

  def shell_sort(a):
      a = a[:]
      n = len(a)
      gap = n // 2
      while gap > 0:
          for i in range(gap, n):
              x = a[i]
              j = i
              while j >= gap and a[j - gap] > x:
                  a[j] = a[j - gap]
                  j -= gap
              a[j] = x
          gap //= 2
      return a

• Notes and tips:

  • Python built-in sort (Timsort) is usually best: stable, O(n log n), exploits runs and nearly-sorted data.
  • Quick Sort in Python can hit recursion limits on adversarial inputs; mitigate with randomized pivot and smaller-first recursion (or switch to iterative).
  • Merge Sort is stable and ideal for linked lists (O(1) extra on lists), but needs O(n) extra on arrays.
  • Heap Sort provides O(n log n) worst-case without extra memory but has larger constant factors than Timsort.
  • For non-comparison sorts (Counting/Bucket/Radix), see the corresponding section in your cheatsheet.

[tpemeja]

https://zaxrosenberg.com/must-know-sorting-algorithms-in-python/

[tpemeja]

https://www.britannica.com/technology/sorting-algorithm

[tpemeja]

https://favtutor.com/blogs/quick-sort-cpp

[tpemeja]

For in-place quick sort, can take random pivot, but it at the end, setting index i to swap back the pivot, compare every number with pivot and if lower swap with value in index and increase index. By increasing it we assure that the index a value equal or higher than the pivot so we can swap