Sorting helps organize data in a specific order. It is used in search, reports, and efficient storage. Different sorting algorithms offer different performance. In this article, we will explain the Time Complexity of Sorting Algorithms in simple words. We will cover Python, Java, and C++ examples.

1. What Is Time Complexity?

Time complexity tells how fast an algorithm runs. It measures the number of steps as input grows. It is written in Big-O notation. For example, O(n²) means steps grow with the square of inputs.

2. Types of Time Complexity

Here are common types:

• O(1): Constant time
• O(n): Linear time
• O(n log n): Log-linear time
• O(n²): Quadratic time

We will now apply these to sorting.

3. Bubble Sort

Bubble Sort compares two numbers and swaps them if needed. It repeats until the list is sorted.

Time Complexity:

• Best Case: O(n) (if already sorted)
• Average Case: O(n²)
• Worst Case: O(n²)

Python Example:

pythonCopyEditdef bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n - i - 1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

Java Example:

javaCopyEditvoid bubbleSort(int arr[]) {
    int n = arr.length;
    for (int i = 0; i < n-1; i++)
        for (int j = 0; j < n-i-1; j++)
            if (arr[j] > arr[j+1]) {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
}

C++ Example:

cppCopyEditvoid bubbleSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++)
        for (int j = 0; j < n-i-1; j++)
            if (arr[j] > arr[j+1])
                swap(arr[j], arr[j+1]);
}

4. Selection Sort

This sort picks the smallest number and places it at the front.

Time Complexity:

• Best Case: O(n²)
• Average Case: O(n²)
• Worst Case: O(n²)

Python Example:

pythonCopyEditdef selection_sort(arr):
    for i in range(len(arr)):
        min_idx = i
        for j in range(i+1, len(arr)):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

5. Insertion Sort

This algorithm builds the final list one item at a time.

Time Complexity:

• Best Case: O(n)
• Average Case: O(n²)
• Worst Case: O(n²)

Java Example:

javaCopyEditvoid insertionSort(int arr[]) {
    for (int i = 1; i < arr.length; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = key;
    }
}

6. Merge Sort

Merge Sort splits the array into halves and merges them back in order.

Time Complexity of Sorting Algorithms like Merge Sort is usually better.

• Best Case: O(n log n)
• Average Case: O(n log n)
• Worst Case: O(n log n)

Python Example:

pythonCopyEditdef merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left = arr[:mid]
        right = arr[mid:]

        merge_sort(left)
        merge_sort(right)

        i = j = k = 0
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                arr[k] = left[i]
                i += 1
            else:
                arr[k] = right[j]
                j += 1
            k += 1

        arr[k:] = left[i:] + right[j:]

7. Quick Sort

Quick Sort picks a pivot and places smaller numbers before it.

Time Complexity:

• Best Case: O(n log n)
• Average Case: O(n log n)
• Worst Case: O(n²)

C++ Example:

cppCopyEditint partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i+1], arr[high]);
    return i + 1;
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

8. Built-in Sort Methods

Languages have built-in sort functions. These are well-optimized.

• Python: sorted() or list.sort() uses TimSort
  • Time Complexity: O(n log n)
• Java: Arrays.sort() uses Dual-Pivot QuickSort
  • Time Complexity: O(n log n)
• C++: std::sort() uses IntroSort
  • Time Complexity: O(n log n)

These are better for most real-world tasks.

9. Time Complexity Comparison Table

Algorithm	Best	Average	Worst	Stable
Bubble Sort	O(n)	O(n²)	O(n²)	Yes
Selection Sort	O(n²)	O(n²)	O(n²)	No
Insertion Sort	O(n)	O(n²)	O(n²)	Yes
Merge Sort	O(n log n)	O(n log n)	O(n log n)	Yes
Quick Sort	O(n log n)	O(n log n)	O(n²)	No
TimSort (Python)	O(n)	O(n log n)	O(n log n)	Yes
IntroSort (C++)	O(n log n)	O(n log n)	O(n log n)	No

10. How to Choose the Right Algorithm?

• Use Merge Sort for large stable data.
• Use Quick Sort for faster average speed.
• Use Insertion Sort for small or nearly sorted lists.
• Use built-in sort functions unless you need control.

Conclusion

The Time Complexity of Sorting Algorithms helps us pick the right tool. Bubble, Selection, and Insertion Sort are simple but slow. Merge and Quick Sort are faster and used often. Built-in functions are highly optimized. Python, Java, and C++ each have their strengths.

Understand your problem and input size. Then pick the sorting method. This ensures better speed and performance in your code.