Essential Sorting Algorithms and String Processing

Sorting Fundamentals

• Stable sorting: Relative order is preserved.
• In-place: Input and output occupy the same memory space.
• Lower bound: N lg N for any comparison-based algorithm.

Common Sorting Algorithms

• Insertion Sort
• Merge Sort
• Quick Sort: Often cited as the most important algorithm of the 21st century.
  • Recursive approach; processes data after the work is done.
  • Uses a random pivot to partition the list into two unsorted sublists, which are then sorted recursively.
• Bubble Sort: A simple, greedy approach to sorting.
• Heap Sort

String Sorting Techniques

Specific properties of strings allow for faster sorting than general-purpose algorithms.

Strings in Java

• Strings are immutable sequences of 16-bit characters.
• Operations: Length (1), Indexing (1), Concatenation (M + N).
• Reversing: Naive approach is O(N²); using StringBuilder (a mutable char array) achieves O(N).
• Comparing: Proportional to the longest common prefix, or O(W) in the worst case.

Alphabets and Radix

• Digital key: A sequence of digits over a fixed alphabet.
• Radix: The number of digits (R) in the alphabet.

Key-Indexed Counting

• Achieves better than N lg N for characters and small numbers.
• Time complexity: O(N + R).
• Space complexity: O(N + R).
• Stable.

Radix Sort Variations

• LSD Radix Sort: Applies key-indexed counting on each column from right to left. Complexity: O(W(N + R)).
• MSD Radix Sort: Processes from left to right using a bucket method to ensure stability.
  • Uses recursive calls on character groups.
  • Can be space-intensive and cache-inefficient.
  • Outperforms LSD for long strings that differ early on.
• 3-Way Radix Quicksort: A character-based Quicksort.
  • Average complexity: 2 N lg N.
  • In-place and not stable.