Introduction to Sorting

Say you have a list of numbers all jumbled up. Sorting just means putting them in order. Small to large, or large to small. That is it. But this simple idea is one of the most useful things you will learn in DSA. So let me show you why we care about it so much.

🤔 What Does Sorting Mean?

Sorting means arranging items in a fixed order. Usually that means numbers going from small to large. We call that ascending order. The other way, large to small, is called descending order.

Think about your phone’s contact list. The names are in A to Z order, right? That is sorting. You did not scroll through 500 random names to find “Riya”. You jumped straight to the R section. The order helped you.

So sorting takes messy data like this:

5  2  9  1  7

And turns it into neat data like this:

1  2  5  7  9

Same numbers. Just arranged in order now.

🎯 Why Do We Need Sorting?

Here is the real pain. Imagine you have a list of a million numbers. You want to check if the number 42 is in there. If the list is random, you have no choice. You check every single number one by one. That is slow.

But if the list is sorted, everything changes. Let me show you what sorted data gives you.

• Fast searching. On a sorted list you can use binary search. Binary search is a way to find an item by cutting the list in half again and again. A million items take about 20 checks instead of a million.
• Easy to show data nicely. Leaderboards, price lists, search results. People want to see things in order. Highest score first, cheapest item first.
• Finding duplicates becomes simple. When equal items are sorted, they sit right next to each other. So you just check neighbours instead of comparing every pair.
• Finding the smallest or largest is instant. In a sorted list they are just at the two ends.

🧠 The Key Words You Need to Know

Before we study any actual sorting algorithm, there are a few words people use a lot. Let me define them in plain language now. So later they will not confuse you.

In-place. A sorting method is in-place when it rearranges the items using almost no extra memory. It moves things around inside the same list instead of building a fresh copy. So it saves space.

Stable. A method is stable when it keeps equal items in their original order. Say two students both scored 90 marks. A stable sort keeps the one who came first still first. This matters when you sort by one thing after another.

Comparison-based. Most sorts are comparison-based. That means they decide the order by comparing two items at a time and asking “which one is bigger?”. Almost every sort you will first learn works this way.

Here is a quick picture of what stable means. Watch the two items that both have the value 2:

Before:  (2a)  (1)  (2b)  (3)
After a stable sort:    (1)  (2a)  (2b)  (3)
After an unstable sort: (1)  (2b)  (2a)  (3)

See how the stable one kept 2a before 2b, just like the start? The unstable one flipped them. Both are sorted by value. But only the stable one kept the original order of the equal items.

📊 The Sorting Algorithms We Will Cover

There is no single “best” sorting algorithm. There are many. They trade off speed, memory, and how simple they are to write. So you start with the simple slow ones to learn the ideas. Then you move to the fast ones.

Here is an overview of the algorithms in this section, with their average time. Do not worry about memorising this table yet. Just notice that the bottom ones are much faster on big lists.

Here n is the number of items in the list. O(n²) means the work grows fast as the list gets bigger. O(n log n) grows much more slowly. That is the big reason merge sort and quick sort win on large data.

💻 You Do Not Always Write It Yourself

Now here is something nice. Every language already comes with a built-in sort. So in real projects you usually just call it. You write your own only when you are learning, or when you have a special need.

Below is the same job in all five languages. We take a small list and sort it from small to large.

#include <stdio.h>
#include <stdlib.h>

// Comparison function: tells qsort which item is bigger
int compare(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

int main() {
    int arr[] = {5, 2, 9, 1, 7};
    int n = 5;

    // qsort is C's built-in sort
    qsort(arr, n, sizeof(int), compare);

    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

1 2 5 7 9

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    vector<int> arr = {5, 2, 9, 1, 7};

    // sort() is C++'s built-in sort from <algorithm>
    sort(arr.begin(), arr.end());

    for (int x : arr) {
        cout << x << " ";
    }
    cout << endl;
    return 0;
}

1 2 5 7 9

import java.util.Arrays;

public class Sort {
    public static void main(String[] args) {
        int[] arr = {5, 2, 9, 1, 7};

        // Arrays.sort is Java's built-in sort
        Arrays.sort(arr);

        System.out.println(Arrays.toString(arr));
    }
}

[1, 2, 5, 7, 9]

def sort_list(arr):
    # sorted() is Python's built-in sort, returns a new sorted list
    return sorted(arr)

numbers = [5, 2, 9, 1, 7]
print(sort_list(numbers))

[1, 2, 5, 7, 9]

const numbers = [5, 2, 9, 1, 7];

// sort with a compare function so numbers order correctly
numbers.sort((a, b) => a - b);

console.log(numbers);

[ 1, 2, 5, 7, 9 ]

⚠️ Common Mistakes to Avoid

When students first meet sorting, the same few slip-ups come up. Watch out for these.

• Thinking there is one best sort. There is not. The right choice depends on your data size and whether you need stability.
• Forgetting that sorting is not free. On a big list it takes real time. So do not sort again and again if the list has not changed.
• Mixing up stable and in-place. They are different ideas. One is about keeping equal items in order. The other is about saving memory.
• In JavaScript, calling .sort() on numbers without a compare function. It sorts them like words and gives the wrong order.

🧩 What You’ve Learned

• ✅ Sorting means arranging items in order, like numbers from small to large.
• ✅ A sorted list lets you search fast with binary search, show data nicely, and find duplicates easily.
• ✅ There are many sorting algorithms, and they differ in speed and memory use.
• ✅ In-place sorts use almost no extra memory, and stable sorts keep equal items in their original order.
• ✅ Most sorts are comparison-based, and every language has a built-in sort you can just call.

🚀 What’s Next?

• Bubble Sort
• Sorting Algorithms Comparison