Sorting Algorithms - Overview

 

📚 What is Sorting?

Sorting means arranging data elements (numbers, words, records, etc.) in a particular order — usually ascending (small to large) or descending (large to small).

For example:

• Unsorted: [5, 2, 9, 1, 6]

• Sorted (Ascending): [1, 2, 5, 6, 9]

• Sorted (Descending): [9, 6, 5, 2, 1]

Sorting is very important because searching becomes faster, and organized data is easier to use.

---

📋 What are Sorting Algorithms?

Sorting algorithms are step-by-step methods or procedures to rearrange elements into a specific order.

They differ based on:

• Time complexity (speed)

• Space complexity (memory usage)

• Technique used (comparison-based, divide and conquer, etc.)

In-Place Sorting

• Definition: Sorting that does not use extra space (or uses very little extra memory, like a few variables).

• The sorting happens within the given array/list itself by modifying it.

• It saves memory.

✅ No extra array used (or very minimal extra memory).

Example:

• Bubble Sort, Insertion Sort, Selection Sort, and Quick Sort are in-place sorting algorithms.

Internal Sorting

• Definition: When all data to be sorted can fit into main memory (RAM), it is called internal sorting.

• Sorting is completely done in memory.

• No need to read/write from disk during sorting.

✅ Entire data is in RAM.

Example:

• You have an array of 1,000 numbers — you sort them fully in memory using any algorithm (like Insertion  Sort or Quick Sort).

• All in RAM → it's internal sorting.

External Sorting

• Definition: When data is too large to fit into main memory (RAM), and sorting involves disk operations, it's called external sorting.

• Data is partially loaded into memory, sorted in pieces, then combined.

❗ Used when data is larger than available RAM.

Example:

• Huge databases (hundreds of GBs).

• Sorting a 1 TB file on a computer with 16 GB RAM.

• Techniques like External Merge Sort are used.

What is Stable Sorting?

Stable sorting means:

✅ If two elements are equal, they keep their original order after sorting.

A sorting algorithm is called stable if it preserves the relative order of records with equal keys.

---

📖 Example:

Suppose you have a list of students:

Name	Marks
Alice	70
Bob	80
Charlie	60

John

80

Now, sort by Marks (ascending).

If stable sort is used, Bob(80) will stay before John (80) — because originally Bob came before John.

After stable sorting:

Name	Marks
Charlie	60
Alice	70
Bob	80
John	80

✅ Order among equal Marks is preserved.

---

🧠 Why Stability is Important?

• In some applications (like multi-level sorting — first by marks, then by name), stability is critical.

• Stability helps maintain earlier ordering when needed.

---

🔥 Which Algorithms are Stable?

Stable Algorithms	Unstable Algorithms
Bubble Sort	Selection Sort
Insertion Sort	Quick Sort (standard)
Merge Sort (standard version)	Heap Sort
Counting Sort

🎯 Quick Tip:

• If you need to preserve original order of equal elements, use a stable sort.

• If order doesn't matter, you can use any sorting algorithm.

---

🎯 Why Sorting Algorithms are Important?

• Efficient searching (especially Binary Search).

• Data analysis.

• Optimizing other algorithms.

• Making reports, charts, or ordered displays.

---

🔥 Common Types of Sorting Algorithms:

Algorithm	Idea	Time Complexity (Best / Average / Worst)	Space Complexity
Bubble Sort	Repeatedly swap adjacent elements if they are in wrong order	O(n) / O(n²) / O(n²)	O(1)
Selection Sort	Select the minimum (or maximum) element and move it to correct place	O(n²) / O(n²) / O(n²)	O(1)
Insertion Sort	Insert each element into its correct position	O(n) / O(n²) / O(n²)	O(1)
Merge Sort	Divide and Conquer (divide list into halves, sort, merge)	O(n log n) / O(n log n) / O(n log n)	O(n)
Quick Sort	Divide and Conquer (choose pivot, partition elements)	O(n log n) / O(n log n) / O(n²)	O(log n)
Heap Sort	Build a heap and repeatedly remove largest element	O(n log n) / O(n log n) / O(n log n)	O(1)
Counting Sort	Count number of occurrences of elements (only for integers)	O(n + k) / O(n + k) / O(n + k)	O(k)
Radix Sort	Sort based on individual digits/characters	O(nk) / O(nk) / O(nk)	O(n + k)

---

Comparison Table

Aspect	In-place Sorting	Internal Sorting	External Sorting
Memory Usage	Very little (almost none)	Enough to hold all data in RAM	RAM + Disk
Data Location	In the same array	Entire data in RAM	Data split between RAM and Disk
Example Algorithms	Bubble Sort, Insertion Sort, Selection Sort	Merge Sort (small arrays), Heap Sort	External Merge Sort, Polyphase Merge