- \n
- Sorting arranges data (numbers, strings, records) into ascending or descending order \u2014 it’s the most tested topic in DSA interviews.<\/li>\n\n\n\n
- Two categories: internal sorting<\/strong> (fits in RAM \u2014 Bubble, Insertion, Quick, Merge) and external sorting<\/strong> (for data too large for memory).<\/li>\n\n\n\n
- Common algorithms: Bubble, Selection, Insertion, Merge, Quick, Heap, Counting, and Radix Sort \u2014 each with different time\/space trade-offs.<\/li>\n\n\n\n
- Quick Sort<\/strong> is fastest on average (O(n log n)) for large, random datasets, but its worst case is O(n\u00b2).<\/li>\n\n\n\n
- Merge Sort<\/strong> and Heap Sort<\/strong> guarantee O(n log n) even in the worst case, and Merge Sort is stable \u2014 Quick Sort isn’t.<\/li>\n\n\n\n
- Sorting appears in ~10\u201315% of coding interview rounds at product companies, often via Quick Sort\/Merge Sort implementation or variations like the Dutch National Flag problem.<\/li>\n<\/ul>\n\n\n\n
What is Sorting in Data Structure?<\/strong><\/h2>\n\n\n\n
![\"\"](\"https:\/\/www.guvi.in\/blog\/wp-content\/uploads\/2025\/11\/Sorting-in-Data-Structure-1-1200x630.png\" "\\"\\"")
<\/figure>\n\n\n\nSorting arranges data so that each element follows a logical sequence \u2014 smallest to largest (ascending) or largest to smallest (descending).<\/p>\n\n\n\n
For example: Input
[8, 2, 4, 9, 3]<\/code> sorted ascending gives[2, 3, 4, 8, 9]<\/code>.<\/p>\n\n\n\nSorted data is what makes binary search possible, speeds up database queries, and is the backbone of features like autocomplete and leaderboard ranking.<\/p>\n\n\n\n
Categories of Sorting<\/strong><\/h2>\n\n\n\n
![\"\"](\"https:\/\/www.guvi.in\/blog\/wp-content\/uploads\/2025\/11\/Types-of-Sorting-1200x630.png\" "\\"\\"")
<\/figure>\n\n\n\nInternal sorting<\/strong> happens entirely in RAM and works for datasets small enough to fit in memory \u2014 Bubble, Insertion, Selection, Quick, and Merge Sort all fall here.<\/p>\n\n\n\n
External sorting<\/strong> is used when data is too large for RAM and lives on disk \u2014 think sorting a 500 GB log file. External Merge Sort and Multiway Merge Sort handle this by sorting chunks and merging them.<\/p>\n\n\n\n
Types of Sorting Algorithms (with Python Code)<\/strong><\/h2>\n\n\n\n
Bubble Sort<\/strong> repeatedly compares adjacent elements and swaps them if they’re out of order. It’s the simplest algorithm to learn but the slowest for real datasets.<\/p>\n\n\n\n
![\"\"](\"https:\/\/www.guvi.in\/blog\/wp-content\/uploads\/2025\/11\/Bubble-Sorting-1200x630.png\" "\\"\\"")
<\/figure>\n\n\n\ndef bubble_sort(arr):\n n = len(arr)\n for i in range(n):\n for j in range(n - i - 1):\n if arr[j] > arr[j + 1]:\n arr[j], arr[j + 1] = arr[j + 1], arr[j]\n return arr<\/code><\/pre>\n\n\n\nSelection Sort<\/strong> finds the smallest element in the unsorted portion and moves it to the front, one pass at a time. Simple, but it always scans the full remaining list.<\/p>\n\n\n\n
![\"\"](\"https:\/\/www.guvi.in\/blog\/wp-content\/uploads\/2025\/11\/Selection-Sorting-1200x630.png\" "\\"\\"")
<\/figure>\n\n\n\nInsertion Sort<\/strong> builds the sorted list one element at a time, inserting each new item into its correct position \u2014 like sorting playing cards in your hand. It’s efficient on small or nearly-sorted arrays.<\/p>\n\n\n\n
![\"\"](\"https:\/\/www.guvi.in\/blog\/wp-content\/uploads\/2025\/11\/Insertion-Sort-1200x630.png\" "\\"\\"")
<\/figure>\n\n\n\nMerge Sort<\/strong> splits the array in half repeatedly, sorts each half, then merges them back together. It’s a reliable, stable choice for large datasets.<\/p>\n\n\n\n
![\"\"](\"https:\/\/www.guvi.in\/blog\/wp-content\/uploads\/2025\/11\/Merge-Sorting-1200x630.png\" "\\"\\"")
<\/figure>\n\n\n\ndef merge_sort(arr):\n if len(arr) <= 1:\n return arr\n mid = len(arr) \/\/ 2\n left, right = merge_sort(arr[:mid]), merge_sort(arr[mid:])\n result, i, j = [], 0, 0\n while i < len(left) and j < len(right):\n if left[i] <= right[j]:\n result.append(left[i]); i += 1\n else:\n result.append(right[j]); j += 1\n result.extend(left[i:])\n result.extend(right[j:])\n return result<\/code><\/pre>\n\n\n\nQuick Sort<\/strong> picks a pivot, moves smaller elements before it and larger ones after, then repeats on each side. It’s usually the fastest in practice for large arrays.<\/p>\n\n\n\n
![\"\"](\"https:\/\/www.guvi.in\/blog\/wp-content\/uploads\/2025\/11\/Quick-Sorting-1200x630.png\" "\\"\\"")
<\/figure>\n\n\n\ndef quick_sort(arr):\n if len(arr) <= 1:\n return arr\n pivot = arr[len(arr) \/\/ 2]\n left = [x for x in arr if x < pivot]\n mid = [x for x in arr if x == pivot]\n right = [x for x in arr if x > pivot]\n return quick_sort(left) + mid + quick_sort(right)<\/code><\/pre>\n\n\n\nHeap Sort<\/strong> builds a max-heap from the data, repeatedly removes the largest element, and rebuilds the heap until everything is sorted.<\/p>\n\n\n\n
![\"\"](\"https:\/\/www.guvi.in\/blog\/wp-content\/uploads\/2025\/11\/Heap-Sorting-1200x630.png\" "\\"\\"")
<\/figure>\n\n\n\n![\"\"](\"https:\/\/www.guvi.in\/blog\/wp-content\/uploads\/2025\/11\/Counting-Sorting-1200x630.png\" "\\"\\"")
<\/figure>\n\n\n\n![\"\"](\"https:\/\/www.guvi.in\/blog\/wp-content\/uploads\/2025\/11\/Radix-Sorting-1200x630.png\" "\\"\\"")
<\/figure>\n\n\n\n