Introduction to Sorting Algorithms

Sorting algorithms are methods used to arrange data in a specific order (usually ascending or descending).

Let's look into classical problem statement:

Given an array $A$ of $N$ elements, rearrange them so that $A[1] \leq A[2] \leq \ldots \leq A[N]$ (or in descending order).

A valid solution must:

1. Reorder elements (not change their values)
2. Produce a fully sorted sequence
3. Do so with correctness and ideally efficiency

Where Sorting Algorithms Are Helpful

Sorting is a foundational tool in computer science and appears in many real tasks:

• Binary search requires sorted data
• Many dynamic programming and greedy algorithms sort first
• Ranking students by scores
• Detecting duplicates (after sorting, equal items are adjacent)
• Sorting points by x-coordinate
• Sorting edges by weight (e.g., Kruskal’s MST algorithm)
• Sorting tasks by deadlines or durations

Simple Sorting Algorithms

• Bubble Sort — swaps adjacent elements if they’re wrong.
• Selection Sort — picks the smallest element and places it correctly.
• Insertion Sort — inserts each element into its correct position in the sorted prefix.