Sorting Algorithms

In this lesson, we’ll explore four different sorting algorithms:

Bubble Sort
Merge Sort
Quick Sort
Counting Sort.

We’ll provide code for each algorithm, followed by a detailed complexity analysis. Each algorithm will be evaluated based on its time and space complexity, helping you understand when to use each one.

1. Bubble Sort

Bubble Sort is a simple comparison-based sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order.

java

import java.util.Arrays;

public class Solution {

  public void 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]) {
          // Swap arr[j] and arr[j + 1]
          int temp = arr[j];
          arr[j] = arr[j + 1];
          arr[j + 1] = temp;
        }
      }
    }
  }

  public static void main(String[] args) {
    int[] arr = { 5, 3, 8, 1, 2 }; // Example array

    Solution solution = new Solution();
    System.out.println("Original array: " + Arrays.toString(arr));

    solution.bubbleSort(arr);

    System.out.println("Sorted array: " + Arrays.toString(arr));
  }
}

Time Complexity for Bubble Sort

Outer loop: The outer loop runs N times, where N is the length of the input array. This contributes a time complexity of for the outer loop.
Inner loop (nested): For each iteration of the outer loop, the inner loop runs N - i - 1 times. In the first iteration, the inner loop runs approximately N - 1 times, in the second iteration N - 2 times, and so on. The total number of comparisons made can be expressed as:

This simplifies to .

Overall time complexity: . The nested loops dominate the runtime, resulting in quadratic time complexity.

Space Complexity for Bubble Sort

The algorithm only uses a few variables (i, j, and temporary variables for swapping), which require constant space.
No additional data structures are used that depend on the input size.

Overall space complexity: . Bubble Sort is an in-place sorting algorithm, so it only requires a constant amount of extra space.

2. Merge Sort

Merge Sort is a divide-and-conquer algorithm that splits the array into halves, recursively sorts each half, and then merges them back together in sorted order.

java

import java.util.Arrays;

public class Solution {

  // Main function that sorts the array using merge sort
  public static void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
      // Find the middle point
      int mid = (left + right) / 2;

      // Sort first and second halves
      mergeSort(arr, left, mid);
      mergeSort(arr, mid + 1, right);

      // Merge the sorted halves
      merge(arr, left, mid, right);
    }
  }

  // Function to merge two halves
  private static void merge(int[] arr, int left, int mid, int right) {
    // Sizes of two subarrays to be merged
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // Create temporary arrays
    int[] leftArr = new int[n1];
    int[] rightArr = new int[n2];

    // Copy data to temporary arrays
    for (int i = 0; i < n1; i++) {
      leftArr[i] = arr[left + i];
    }
    for (int j = 0; j < n2; j++) {
      rightArr[j] = arr[mid + 1 + j];
    }

    // Merge the temporary arrays back into arr
    int i = 0, j = 0, k = left;
    while (i < n1 && j < n2) {
      if (leftArr[i] <= rightArr[j]) {
        arr[k] = leftArr[i];
        i++;
      } else {
        arr[k] = rightArr[j];
        j++;
      }
      k++;
    }

    // Copy remaining elements of leftArr, if any
    while (i < n1) {
      arr[k] = leftArr[i];
      i++;
      k++;
    }

    // Copy remaining elements of rightArr, if any
    while (j < n2) {
      arr[k] = rightArr[j];
      j++;
      k++;
    }
  }

  // Main method to test the merge sort algorithm
  public static void main(String[] args) {
    int[] arr = { 12, 11, 13, 5, 6, 7 }; // Example array
    System.out.println("Original array: " + Arrays.toString(arr));

    mergeSort(arr, 0, arr.length - 1);

    System.out.println("Sorted array: " + Arrays.toString(arr));
  }
}

Time Complexity for Merge Sort

Divide Step:
- The mergeSort function splits the array into two halves.
- Time Complexity for Division: for calculating mid and slicing arrays.
- This division step is performed at each recursive level, with each level having approximately divisions for an input of size .
Recursive Calls:
- The function recursively calls mergeSort on both the left and right halves.
- Number of Levels: The array is divided until each subarray has one element, resulting in approximately levels of recursion.
Merge Step:
- The merging process iterates over both halves and sorts them.
- Time Complexity for Merging: at each level since all elements are processed once during merging.
- Each level processes the entire array of size N.

Overall Time Complexity:

The merging process runs at each level, and there are levels of recursion:

Space Complexity for Merge Sort

Auxiliary Space for Left and Right Halves:
- At each level of recursion, space is used for creating the left and right subarrays (arr[:mid] and arr[mid:]).
- This leads to additional space for splitting arrays at each level of recursion.
Recursive Call Stack:
- The depth of the recursion stack is due to the binary splitting.
- Each call adds a frame to the stack, but these do not contribute to more than space.

Overall Space Complexity:

The merge process and auxiliary space for storing left and right halves contribute to .
The recursive stack contributes space.

Total Space Complexity:

3. Quick Sort

Quick Sort is a highly efficient sorting algorithm that picks a pivot and partitions the array into subarrays, sorting them recursively.

java

import java.util.Arrays;

public class Solution {
    // Main function to sort an array using Quick Sort
    public static void quickSort(int[] arr, int low, int high) {
        if (low < high) {
            // Partition the array and get the pivot index
            int pi = partition(arr, low, high);

            // Recursively sort elements before and after partition
            quickSort(arr, low, pi - 1);
            quickSort(arr, pi + 1, high);
        }
    }

    // Function to partition the array
    public static int partition(int[] arr, int low, int high) {
        int pivot = arr[high]; // Pivot element
        int i = low - 1; // Index of the smaller element

        for (int j = low; j < high; j++) {
            // If the current element is smaller than or equal to the pivot
            if (arr[j] <= pivot) {
                i++;
                // Swap arr[i] and arr[j]
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        // Swap arr[i + 1] and arr[high] (or pivot)
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;

        return i + 1; // Return the partition index
    }

    public static void main(String[] args) {
        int[] arr = {10, 7, 8, 9, 1, 5}; // Example array

        Solution solution = new Solution();
        System.out.println("Original array: " + Arrays.toString(arr));

        solution.quickSort(arr, 0, arr.length - 1);

        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}

Time Complexity for Quick Sort

Partition Step:
- The array is partitioned into left, middle, and right subarrays based on the pivot.
- Time Complexity for Partitioning: for each call as it requires iterating through the array to build the subarrays left, middle, and right.
Recursive Calls:
- The quickSort function is recursively called on left and right subarrays.
- Best and Average Case:
  - If the pivot splits the array into two roughly equal parts, each call processes elements, leading to levels of recursion.
  - Total Time Complexity: .
- Worst Case:
  - If the pivot is the smallest or largest element (e.g., already sorted or reverse-sorted arrays), one partition will have elements, leading to levels of recursion.
  - Total Time Complexity in Worst Case: .

Overall Time Complexity:

Best and Average Case: .
Worst Case: .

Space Complexity for Quick Sort

Auxiliary Space:
- The partitioning step creates new subarrays (left, middle, right) at each level, requiring additional space proportional to for each partition.
Recursive Call Stack:
- The depth of the recursion stack is in the best and average cases, but can be in the worst case for highly unbalanced splits.

Overall Space Complexity:

Best and Average Case: for the recursion stack.
Worst Case: due to the maximum recursion depth.

Total Space Complexity:

Auxiliary Space: for subarrays created at each level.

4. Counting Sort

Counting Sort is a non-comparison-based sorting algorithm that counts the occurrences of each element and uses this count to place them in the correct position.

java

import java.util.Arrays;

public class Solution {
    public static void countingSort(int[] arr) {
        int max = findMax(arr);
        int[] count = new int[max + 1];

        // Count the occurrences
        for (int num : arr) {
            count[num]++;
        }

        // Build the sorted array
        int index = 0;
        for (int i = 0; i < count.length; i++) {
            while (count[i] > 0) {
                arr[index++] = i;
                count[i]--;
            }
        }
    }

    private static int findMax(int[] arr) {
        int max = arr[0];
        for (int num : arr) {
            if (num > max) {
                max = num;
            }
        }
        return max;
    }

    public static void main(String[] args) {
        int[] arr = {4, 2, 2, 8, 3, 3, 1}; // Example array

        System.out.println("Original array: " + Arrays.toString(arr));

        countingSort(arr);

        System.out.println("Sorted array: " + Arrays.toString(arr));
    }
}

Time Complexity for Counting Sort

Finding the Maximum Element (max(arr)):
- Time Complexity: – This step iterates through the array once to find the maximum value.
Creating the Count Array:
- Time Complexity: , where is the value of the maximum element in the array. This step initializes an array of size K + 1 to zero.
Counting the Occurrences:
- The for loop that iterates through arr and increments the count in the count array runs in:
  - Time Complexity: – It iterates through each element in the input array once.
Building the Sorted Array:
- The second for loop iterates over the count array and extends sorted_arr based on the counts.
- Time Complexity: – The loop runs times, and extending sorted_arr takes across all iterations.

Overall Time Complexity:

The total time complexity is:

This makes Counting Sort efficient when (the range of input values) is not significantly larger than .

Space Complexity for Counting Sort

Count Array:
- The count array is created with a size of , where is the maximum element in arr.
- Space Complexity: – This space depends on the range of input values.
Sorted Array:
- The sorted_arr is created to store the sorted output.
- Space Complexity: – It stores the sorted elements of the input array.

Overall Space Complexity:

The total space complexity is:

Which Sorting Algorithm is Better?

Bubble Sort: Simple to implement but inefficient for large datasets ().
Merge Sort: Reliable performance but uses space.
Quick Sort: Efficient for most cases with time, but worst case is . Uses less space ().
Counting Sort: Ideal for small ranges of integers; time but uses more space ().

Best Overall Choice: Quick Sort for general cases due to its efficiency and average time. Merge Sort is a close second for guaranteed performance, especially when space is not a concern.

🤖 Don't fully get this? Learn it with Claude

Stuck on Sorting Algorithms? Open Claude, copy a block below, and it'll teach you this exact concept — visually and interactively.

🎨 Explain it visually

Build the mental picture, not memorization.

I just read a lesson on **Sorting Algorithms** (DSA) and want to truly understand it. Explain Sorting Algorithms from first principles using ONE vivid real-world analogy and a visual mental model — draw it as ASCII art or a clear step-by-step diagram — with a concrete example using real numbers. Then ask me one question to check I got the mental picture, and wait for my reply. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🤔 Walk me through it (interactive)

Socratic — adapts to where you're stuck.

Teach me **Sorting Algorithms** interactively. Ask me ONE guiding question at a time, wait for my answer, and adapt to my confusion — build the idea with me step by step instead of explaining it all at once. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🧪 Quiz me & fix my gaps

Active recall exposes what you missed.

Quiz me on **Sorting Algorithms** with 5 questions, easy to tricky, ONE at a time. Tell me if each answer is right; at the end, explain clearly what I got wrong and why. If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

🧠 Make it stick

Intuition + hook + flashcards for long-term memory.

Help me remember **Sorting Algorithms** for the long term: give the one-sentence intuition, a memorable hook/mnemonic, a tiny worked example, and 3 active-recall flashcards (Q -> A). If you're unsure or a claim isn't standard, say so and reason from first principles instead of guessing.

📝 My notes

← Quiz (4)Graph Algorithms →