Sorting Algorithms

A sorting algorithm is a way to arrange elements of an array in a specific order, usually ascending or descending. It helps in organizing data so that other operations like searching and processing become easier and faster.

Sorting algorithms may look similar at first, but each one follows a different idea. Understanding how they work with small examples makes them easier to grasp.

---

Merge Sort

Merge Sort divides the array into smaller parts and then merges them back in sorted order.

It keeps splitting the array until each part has one element. Then it starts merging them step by step in a sorted way.

Example:
[4, 2, 1, 3]

• Split → [4, 2] and [1, 3]
• Split again → [4] [2] [1] [3]
• Merge → [2, 4] and [1, 3]
• Final merge → [1, 2, 3, 4]

Key Points:

• Uses divide and conquer
• Always O(n log n)
• Uses extra space for merging

---

Quick Sort

Quick Sort picks a pivot and places it in the correct position.

Then it rearranges the array so that smaller elements are on the left and larger ones are on the right. The same process is repeated recursively.

Example:
[4, 2, 5, 1, 3]

• Pick pivot = 3
• Left → [2, 1], Right → [4, 5]
• Sort both sides → [1, 2] and [4, 5]
• Final → [1, 2, 3, 4, 5]

Key Points:

• Very fast in practice
• Average time O(n log n)
• Worst case O(n²) if pivot is bad
• In-place (no extra space needed)

---

Heap Sort

Heap Sort first builds a max heap and then extracts elements one by one.

A max heap ensures the largest element is always at the top. We swap it with the last element and reduce the heap size.

Example:
[4, 1, 3, 2]

• Build max heap → [4, 2, 3, 1]
• Remove 4 → [1, 2, 3] → heapify → [3, 2, 1]
• Remove 3 → [1, 2] → heapify → [2, 1]
• Final → [1, 2, 3, 4]

Key Points:

• Time complexity O(n log n)
• No extra space required
• Not stable

---

Counting Sort

Counting Sort counts occurrences of each number instead of comparing elements.

It works best when the range of numbers is small.

Example:
[2, 1, 2, 0, 1]

• Count → 0:1, 1:2, 2:2
• Rebuild → [0, 1, 1, 2, 2]

Key Points:

• Time complexity O(n + k)
• Very fast for small ranges
• Not comparison-based
• Uses extra space

---

Conclusion

Each algorithm uses a different idea:

• Merge Sort - divide and merge
• Quick Sort - partition around pivot
• Heap Sort - use heap structure
• Counting Sort - count frequencies

Knowing these patterns helps in choosing the right approach.