Space Complexity and Stability

Beyond just time, two other crucial characteristics define an algorithm's profile: how much memory it uses (space complexity) and how it handles duplicate elements (stability). These factors can be just as important as speed when choosing the right sorting algorithm for a particular problem.

Space Complexity

Space complexity measures the amount of extra memory an algorithm needs to run, relative to the input size. It answers the question: if I double the size of my input array, will I need double the memory?

For Bubble Sort, the answer is no. Take another look at our Java code. To sort the array, the only extra memory we use is for a few variables like n, i, j, temp, and swapped.

int n = arr.length; // One variable
boolean swapped;    // One variable
int temp;           // One variable for swapping
// Loop counters 'i' and 'j' also take up constant space

Crucially, the amount of memory these variables occupy does not change, regardless of whether the array has 10 elements or 10 million elements. This is known as constant space.

• The Complexity: Because the memory usage is constant and does not scale with the input size 'n', the space complexity of Bubble Sort is .
• In-Place Algorithm: Algorithms with space complexity are also called in-place algorithms. This means they sort the data within the original array structure, without needing to create a large auxiliary array to hold temporary data. This memory efficiency is one of Bubble Sort's key advantages.

Stability

A sorting algorithm is considered stable if it maintains the original relative order of equal elements in the sorted output. This is an important, though sometimes subtle, property.

Imagine you have a list of students, and you first sort them by name. Then, you sort them again by their final score. If two students have the same score, a stable sorting algorithm would guarantee that their original alphabetical order is preserved.

Bubble Sort is a stable sorting algorithm. Why?

The reason lies in its core comparison logic: if (arr[j] > arr[j+1]). A swap only happens if the element on the left is strictly greater than the element on the right. It never swaps elements if they are equal. This ensures that identical elements will pass over each other without ever changing their initial order.

Let's see a quick example:

Suppose we have an array of objects, sorted by a primary key, and we want to sort by a secondary value. Let's represent them as (value, original_position).

Initial Array: [(5, A), (2, B), (5, C), (1, D)]

Here we have two elements with the value 5. The one at position A came before the one at position C.

• Pass 1:
  • (5, A) vs (2, B)     Swap      [(2, B), (5, A), (5, C), (1, D)]
  • (5, A) vs (5, C)     No Swap (because 5 is not > 5)      [(2, B), (5, A), (5, C), (1, D)]
  • (5, C) vs (1, D)     Swap     [(2, B), (5, A), (1, D), (5, C)]
• After more passes, the final sorted array will be: [(1, D), (2, B), (5, A), (5, C)]

As you can see, (5, A) still comes before (5, C) in the final output. The original order of the equal elements was preserved. This Bubble Sort stability is a valuable feature in many real-world data processing scenarios.