Unit 6: Efficient Sorting Algorithms & Analysis

I. Orientation — Ordering as a Foundation for Efficient Algorithms

Sorting arranges elements according to a specified order, usually nondecreasing order. Efficient sorting is central to competitive programming because an ordering often converts an expensive search, grouping, or comparison task into a linear scan. The main comparison-based algorithms in this unit achieve approximately (O(n \log n)) time, where (n) is the number of elements.

• Input model: The input contains (n) elements, which may be numbers, characters, strings, or records with sortable keys.
• Ordering convention: Ascending order means (a_0 \leq a1 \leq \cdots \leq a{n-1}); descending order reverses this relation.
• Complexity focus: Time complexity measures comparisons and element movement; auxiliary space measures memory beyond the input.
• Stability: A stable sort preserves the relative order of equal-key records. This matters when sorting records by multiple fields.
• In-place behavior: An in-place algorithm uses (O(1)) or small auxiliary memory, excluding recursion stack where stated.
• Comparison limitation: Comparison sorting has a lower bound of (\Omega(n \log n)) in the general case because it must distinguish among (n!) possible orders.

II. (O(n \log n)) Sorting Algorithms — Divide, Organize, and Combine

A. Introduction to O(n logn) Sorting Algorithms

The purpose of (O(n \log n)) sorting algorithms is to reduce the number of comparisons by repeatedly dividing the input or selecting effective partitions.

• Logarithmic depth: Dividing (n) elements into two roughly equal parts creates about (\log_2 n) levels. For (n=8), the levels are (8 \rightarrow 4 \rightarrow 2 \rightarrow 1).
• Linear work per level: Merge sort processes all (n) elements during each merge level, producing (O(n \log n)).
• Average versus worst case: Merge sort guarantees (O(n \log n)), while quick sort has (O(n \log n)) average time but can reach (O(n^2)).
• Lower-bound significance: Algorithms such as merge sort and quick sort are asymptotically optimal for comparison sorting in the general model.
• Practical factors: Cache behavior, recursion overhead, stability, memory usage, and pivot quality can matter as much as the asymptotic formula.

III. Merge Sort — Guaranteed Divide-and-Conquer Sorting

Merge sort divides the array into smaller arrays, sorts them, and combines two sorted arrays through a linear-time merge operation.

A. Iterative & Recursive Merge Sort

Both forms implement the same recurrence, but they differ in control flow and memory behavior.

• Recursive strategy: For a range ([l,r]), compute (m=\lfloor(l+r)/2\rfloor), recursively sort ([l,m]) and ([m+1,r]), then merge them.

  • Base case: If (l \geq r), the range has at most one element and is already sorted.
  • Recurrence: (T(n)=2T(n/2)+O(n)), which solves to (O(n\log n)).

• Iterative strategy: Start with sorted runs of width (1), then merge adjacent runs of widths (1,2,4,8,\ldots) until the width is at least (n).

  • Example progression: For (n=8), merge runs of sizes (1), then (2), then (4).

• Merge operation: Maintain pointers (i) and (j) into the left and right sorted halves; copy the smaller value into the output.

• Stability rule: Select from the left half when values are equal, using left[i] <= right[j]; this preserves original order.

• Complexity: Time is (O(n\log n)) in best, average, and worst cases; auxiliary array space is (O(n)), with recursive stack space (O(\log n)).

• Pseudocode:
  

  TEXT

  mergeSort(A, left, right):
      if left >= right:
          return
      mid = (left + right) // 2
      mergeSort(A, left, mid)
      mergeSort(A, mid + 1, right)
      merge(A, left, mid, right)

  
  Here, A is the array, and left, mid, and right are inclusive indices.

• Iterative pseudocode:
  

  TEXT

  width = 1
  while width < n:
      for start = 0; start < n; start += 2 * width:
          mid = min(start + width, n)
          end = min(start + 2 * width, n)
          merge(A, start, mid, end)
      width *= 2

  
  Here, width is the current run size, and end is treated as exclusive.

B. Applications and Limitations

Merge sort is useful when predictable running time and stability are more important than constant memory.

• Linked lists: Merging lists can be done by pointer changes, avoiding an (O(n)) temporary array.
• External sorting: Large files can be sorted in chunks and merged because merge sort accesses data sequentially.
• Inversion counting: During merging, if a right-half element precedes remaining left-half elements, it forms inversions with all remaining left elements.
• Main limitation: Standard array merge sort needs (O(n)) auxiliary storage, which can be significant for (n=10^6).
• Best use: Choose it when worst-case (O(n\log n)), stability, or predictable performance is required.

IV. Quick Sort — Partition-Based Sorting

Quick sort selects a pivot, partitions the range into elements on either side of the pivot, and recursively sorts the resulting ranges.

A. Quick Sort

The partition invariant is that elements placed before the pivot are no greater than it, while elements after it are no smaller, depending on the chosen partition scheme.

• Lomuto partition: Choose pivot (A[r]); maintain index (i) for the next position of an element (\leq) pivot, then swap the pivot into position (i+1).
• Hoare partition: Use two pointers moving inward; swap misplaced values. It often performs fewer swaps but returns a partition boundary rather than the pivot’s final position.
• Average complexity: If partitions are reasonably balanced, (T(n)=2T(n/2)+O(n)=O(n\log n)).
• Worst case: A pivot that is always the smallest or largest gives (T(n)=T(n-1)+O(n)=O(n^2)), common for already sorted input with an endpoint pivot.
• Randomization: Choosing a random pivot makes consistently poor partitions unlikely and gives expected (O(n\log n)) time.
• Space: In-place partitioning uses (O(1)) auxiliary array space; recursion requires (O(\log n)) expected stack space and (O(n)) in the worst case.
• Stability: Standard quick sort is not stable because swaps can change the order of equal values.
• Optimization: Recurse first on the smaller partition and process the larger iteratively to limit stack depth.
• Pseudocode:
  
  TEXT

  quickSort(A, low, high):
      if low >= high:
          return
      p = partition(A, low, high)
      quickSort(A, low, p - 1)
      quickSort(A, p + 1, high)

  
  Here, p is the pivot’s final index under a Lomuto-style partition.

V. Specialized Sorting Tasks — Ordering by Constraints and Keys

Sorting problems often require a custom key rather than ordinary numerical order. The comparator must represent the exact ordering rule.

A. Sorting Elements by Frequency

Sorting Elements by Frequency orders values according to how often they occur, commonly from highest frequency to lowest, with a tie-break rule such as first appearance or numerical value.

• Frequency construction: Use a hash map (f[x]) to count each value (x) in (O(n)) expected time.
• Comparator key: A common descending-frequency rule is:
  [
  x \prec y \quad \text{if } f[x] > f[y]
  ]
  If frequencies tie, compare (x<y) or compare first-occurrence positions.
• Expansion method: Sort distinct values, then append each value (f[x]) times. If there are (d) distinct values, sorting costs (O(d\log d)), and expansion costs (O(n)).
• Record method: Store pairs ((x,f[x])) and sort the records using a comparator that accesses the frequency field.
• Worked example: For [4, 5, 6, 5, 4, 4], frequencies are (f[4]=3), (f[5]=2), (f[6]=1); descending-frequency output is [4,4,4,5,5,6].
• Correctness condition: The comparator must be transitive; contradictory rules can cause undefined behavior in library sorting routines.

B. Finding Minimum Length Sorted Sub-array to Sort an Array

This task finds the shortest contiguous sub-array which, when sorted, makes the entire array sorted.

• Initial boundaries: Scan from the left until A[i] > A[i+1]; this first index is the tentative left boundary. Scan from the right until A[j-1] > A[j]; this gives the tentative right boundary.
• Interior extremes: Compute subMin and subMax within [left, right].
• Boundary expansion: Move left leftward while an earlier element is greater than subMin; move right rightward while a later element is smaller than subMax.
• Worked example: For [1, 2, 6, 5, 5, 8, 9], the disorder is [6,5,5], with subMin=5 and subMax=6; sorting indices 2..4 produces [1,2,5,5,6,8,9].
• Complexity: The method uses (O(n)) time and (O(1)) extra space, unlike sorting every candidate sub-array.
• Edge case: If no inversion exists, the array is already sorted and the minimum length is (0).

C. Sorting Strings

Sorting Strings means ordering character sequences lexicographically, where comparison proceeds from the first differing character.

• Lexicographic rule: Compare s[i] and t[i] at the first index (i) where they differ; the string with the smaller character comes first.
• Prefix rule: If one string is a prefix of another, the shorter string comes first: "app" < "apple".
• Complexity: Sorting (n) strings by comparison costs (O(n\log n)) comparisons; each comparison may cost (O(L)), where (L) is the compared prefix length.
• Memory behavior: In languages with immutable strings, sorting references avoids copying complete strings during swaps.
• Custom keys: Sort by length, number of vowels, or a normalized form by supplying a key function or comparator.
• Pitfall: Do not compare only string lengths when lexicographic order is required; "zoo" and "apple" both have length three but differ lexicographically.

D. Case-specific sorting of strings

Case-specific sorting of strings applies a defined policy to uppercase and lowercase characters rather than relying blindly on language-specific character codes.

• ASCII ordering: Uppercase letters 'A'–'Z' have codes 65–90, while lowercase letters 'a'–'z' have codes 97–122; direct sorting therefore places all uppercase letters before lowercase letters.
• Case-insensitive order: Compare lower(s) and lower(t) first, then use the original string as a tie-breaker when deterministic output is required.
• Case preservation: A case-insensitive sort changes positions, not characters; "bAca" may be ordered by keys "baca" while retaining its original spellings.
• Stable policy: For equal normalized keys such as "A" and "a", a stable sort preserves their input order.
• Comparator key example:
  
  TEXT

  key(s) = (lowercase(s), s)

  
  Here, lowercase(s) provides primary case-insensitive order and s provides a deterministic secondary order.
• Locale issue: Alphabetical order for accented or non-English characters may differ from ASCII order; use locale-aware comparison when the specification requires it.

VI. Difference-Based Pair Counting — Hashing and Ordered Search

A. Count Distinct Pairs with Difference of K

Count Distinct Pairs with Difference of K asks for the number of unordered value pairs ((x,y)) satisfying (|x-y|=k), counting each value pair once.

• Positive difference condition: For (k>0), count distinct (x) such that (x+k) exists; each pair is represented exactly once as ((x,x+k)).
• Set method: Insert all array values into a set, then test x + k for every distinct x.
  • Complexity: Expected time is (O(n)), and auxiliary space is (O(d)), where (d) is the number of distinct values.
• Frequency method: A frequency map is useful when the input contains duplicates, but each key must contribute at most one pair.
• Zero difference: If (k=0), count distinct values appearing at least twice, because the pair is ((x,x)) and requires two occurrences.
• Negative (k): Since the condition uses an absolute difference, replace (k) by (|k|); some problem statements instead reject negative values.
• Worked example: For [1,5,3,4,2,2] and (k=2), distinct values are {1,2,3,4,5}; valid pairs are (1,3), (2,4), and (3,5), so the count is 3.
• Sorting alternative: Sort the array and use two pointers, skipping duplicates. This takes (O(n\log n)) time and can use (O(1)) auxiliary space after sorting.
• Correctness distinction: Counting index pairs would count duplicate occurrences separately; “distinct pairs” counts value pairs, so [1,1,3] with (k=2) contributes only (1,3).
• Pseudocode:
  
  TEXT

  countPairs(A, k):
      k = abs(k)
      frequency = map of value frequencies
      answer = 0
      for x in frequency:
          if k == 0 and frequency[x] >= 2:
              answer += 1
          else if k > 0 and x + k exists in frequency:
              answer += 1
      return answer

  
  Here, A is the input array, k is the required difference, and frequency stores occurrence counts.