Updated on
Bubble sort is a sorting algorithm that compares adjacent elements and swaps them when they are in the wrong order. In C#, it takes two nested loops and one temporary variable, and on random data its running time grows with the square of the array size.
Sorting arrays is quite a common problem in programming, and bubble sort is usually the first algorithm we learn for it. It is simple to implement and slow on large arrays, and our benchmark at the end measures how slow.
Let’s dive in.Â
What Is the Bubble Sort Algorithm?
So, how does bubble sort in C# work?
Let’s say we want to sort an array that has seven elements:
int[] array = { 73, 57, 49, 99, 133, 20, 1 };
Using the bubble sort algorithm, let’s start by comparing 73 and 57. 57 is less than 73, so we swap their positions and the array becomes:
57, 73, 49, 99, 133, 20, 1
49 is less than 73, which triggers the algorithm to swap their positions:
57, 49, 73, 99, 133, 20, 1
73 is less than 99 while 99 is less than 133, so the algorithm skips these positions. Next, we compare 133 with 20 and swap their positions as 20 is less than 133:
57, 49, 73, 99, 20, 133, 1
Since 1 is less than 133, the algorithm swaps their positions:
57, 49, 73, 99, 20, 1, 133
The bubble sort algorithm repeats this process until all the elements are in the correct order with the final result being:
1, 20, 49, 57, 73, 99, 133Â
Every pass moves the largest value it meets to the end, so after the first pass 133 sits in its final place, and each later pass has one element less to check. Our seven elements need six passes.

Bubble sort on our seven-element array: each pass moves the largest remaining value to the end.
How to Implement Bubble Sort in C#?
To implement bubble sort in C#, we need two nested for loops and a temporary variable for the swap.
The inner loop walks the array from the start and compares each element with its right neighbour. When the left one is bigger, we swap the two through the temporary variable. By the end of the pass, the largest value has travelled to the last position.
The outer loop repeats that pass. Each pass puts one more value in its final place at the end, so on pass i the inner loop can stop i positions earlier. That is where its condition, j < n - i - 1, comes from.
An array of n elements needs at most n - 1 passes.
The comparison is a strict >, so two equal values never swap and keep their original order. That makes bubble sort a stable sort.
The method sorts the array in place and returns the same array instance it was given.
We are going to define an integer array property NumArray in a Bubble class of a new console app, that we are going to use to implement the bubble sort algorithm:
public int[] NumArray { get; set; } = [];
Let’s create a method in the same class that implements the bubble sort algorithm in C# that sorts the values in the NumArray property:
public int[] SortArray()
{
var n = NumArray.Length;
for (int i = 0; i < n - 1; i++)
for (int j = 0; j < n - i - 1; j++)
if (NumArray[j] > NumArray[j + 1])
{
var tempVar = NumArray[j];
NumArray[j] = NumArray[j + 1];
NumArray[j + 1] = tempVar;
}
return NumArray;
}
The variable n holds the size of the array while the tempVar variable holds values temporarily during the swap process. Let’s use our array example to understand how the code works:
The outer loop iterates through the array while the inner loop compares adjacent elements. Since 57 is less than 73, they swap their positions and the inner loop continues comparing adjacent values until it gets to the last element of that array. For each iteration of the outer loop, the inner loop iterates while performing comparisons.
In a test method of an MSTest project that references our app, let’s check if our loop performed correctly:
var array = new int[] { 73, 57, 49, 99, 133, 20, 1 };
var expected = new int[] { 1, 20, 49, 57, 73, 99, 133 };
var sortFunction = new Bubble();
sortFunction.NumArray = array;
var sortedArray = sortFunction.SortArray();
Assert.IsNotNull(sortedArray);
CollectionAssert.AreEqual(expected, sortedArray);
What Is the Time and Space Complexity of Bubble Sort?
Bubble sort runs in O(N²) time in the average and the worst case, and it needs O(1) extra space.
The space part is short. The algorithm sorts in place, and the only extra storage is the tempVar variable that holds a value during a swap.
The time comes from the two nested loops. Our SortArray() method makes n(n − 1) / 2 comparisons whatever order the input is in. For 2,000 elements that is 1,999,000 comparisons, sorted array or not.
The best case of O(N) belongs to the optimized version we build later. On an array that is already sorted, it stops after one pass and 1,999 comparisons, because that pass makes no swaps.
On random input the early exit barely helps. When we counted on 20 random arrays of 2,000 numbers, the optimized method still needed between 1,872 and 1,998 of its 1,999 possible passes.
In practice, ten times more elements means roughly a hundred times more work.
Best Case Complexity: this case occurs when we want to sort an array that is already in required order. Only the optimized version takes advantage of it: it traverses the array once without swapping values and stops, which means, its complexity is O(N). Our first version still runs every pass, so it stays at O(N²).
Average Case Complexity: this case occurs when the elements are in random order. The bubble sort algorithm performs comparisons while swapping some values, which means, it has a complexity of O(N²).
Worst Case Complexity: this scenario occurs when we have a list of numbers that are in descending order and we need to sort them in ascending order. The algorithm compares all elements and swaps every pair it compares, which means, it has a complexity of O(N²).
Advantages and Disadvantages
The bubble sort algorithm is easy to learn and implement. On top of that, it has little memory overhead as the sorting is done in place, which is similar to selection sort. This attribute comes in handy in memory-intensive applications. The optimized version performs well in cases where an array is almost in order, as that is close to the best case complexity scenario. A value moves only one position to the left per pass, though, so one small number stuck at the end of an otherwise sorted array still forces every pass: for 2,000 elements, all 1,999 of them.
On the other hand, the bubble sort algorithm has high levels of time complexity O(N²), which is inefficient when compared to other algorithms such as merge sort, which runs in O(N log N).
Bubble sort has one property that Array.Sort() lacks: it is stable, so equal values keep their original order. The Microsoft Learn page for Array.Sort() says the method “performs an unstable sort; that is, if two elements are equal, their order might not be preserved.” When the order of equal keys matters, we need a stable method, and we compare the options in our article on sorting a list by a property.
How to Optimize the Bubble Sort Algorithm in C#?
We can see that the bubble sort algorithm still iterates even in cases where an array is already in order. We can optimize the swapping process by checking whether we need to swap elements or not. Let’s optimize our previous implementation in a second method of the same class and see what’s different about it:
public int[] SortOptimizedArray()
{
var n = NumArray.Length;
bool swapRequired;
for (int i = 0; i < n - 1; i++)
{
swapRequired = false;
for (int j = 0; j < n - i - 1; j++)
if (NumArray[j] > NumArray[j + 1])
{
var tempVar = NumArray[j];
NumArray[j] = NumArray[j + 1];
NumArray[j + 1] = tempVar;
swapRequired = true;
}
if (swapRequired == false)
break;
}
return NumArray;
}
We introduce a boolean value swapRequired to track whether we need to swap the elements or not. The swapRequired variable becomes true when we swap elements, otherwise, it’s set to false. In iterations where swapping is not required, the swapRequired will be false, which means, the array elements are in order and we break the loop before it finishes to the end. On a sorted or nearly sorted array, this saves a lot of time. On a random array, a pass with no swaps usually comes only near the very end, so the saving is small, as our benchmark shows.
In a second test method, let’s check if our optimal bubble sort algorithm performs correctly:
var array = new int[] { 73, 57, 49, 99, 133, 20, 1 };
var expected = new int[] { 1, 20, 49, 57, 73, 99, 133 };
var sortFunction = new Bubble();
sortFunction.NumArray = array;
var sortedArray = sortFunction.SortOptimizedArray();
Assert.IsNotNull(sortedArray);
CollectionAssert.AreEqual(expected, sortedArray);
Bubble Sort Performance
Let’s verify the bubble sort algorithm has a time complexity of O(N²) by measuring the time it takes for the algorithm to sort an array with BenchmarkDotNet.
First, let’s write a method in our Bubble class to generate a set of random numbers that are going to be added into the array:
public static int[] GenerateRandomNumber(int size)
{
var array = new int[size];
var rand = new Random();
var maxNum = 10000;
for (int i = 0; i < size; i++)
array[i] = rand.Next(maxNum + 1);
return array;
}
The GenerateRandomNumber method takes an integer as its sole input. Using the inbuilt Random class, we generate integer values (from 0 to 10000) that we’re going to put into the array.
To simulate a scenario where we have a sorted array, we are going to define a method in the same class that generates a sequence of elements:
public static int[] GenerateSortedNumber(int size)
{
var array = new int[size];
for (int i = 0; i < size; i++)
array[i] = i;
return array;
}
Our sort methods work in place, and BenchmarkDotNet calls a benchmark method many times in a row. If every call sorted the same array, only the first call would see random numbers. Every call after it would sort an array that is already sorted, and the optimized version would look far faster than it really is.
So, we keep each generated array as a source and copy it into a working array at the start of every call:
public class BubbleBenchmarks
{
private readonly Bubble _bubble = new();
private int[] _source = [];
private int[] _work = [];
[Params(200, 2_000, 20_000)]
public int Size { get; set; }
[Params("Random", "Sorted")]
public string Input { get; set; } = "Random";
[GlobalSetup]
public void Setup()
{
_source = Input == "Random"
? Bubble.GenerateRandomNumber(Size)
: Bubble.GenerateSortedNumber(Size);
_work = new int[Size];
}
[Benchmark]
public int[] SortArray()
{
_source.CopyTo(_work, 0);
_bubble.NumArray = _work;
return _bubble.SortArray();
}
[Benchmark]
public int[] SortOptimizedArray()
{
_source.CopyTo(_work, 0);
_bubble.NumArray = _work;
return _bubble.SortOptimizedArray();
}
}
Setup() runs once for each benchmark method and each combination of Size and Input, before the timed calls, and fills the source array with random or sorted numbers. The copy costs O(N) time, which disappears next to an O(N²) sort. It is a visible part of the time only in the one case where the sort itself is O(N): the optimized method on a sorted array.
The class goes in its own file in our console app. We add the BenchmarkDotNet package to the app, start the class file with using BenchmarkDotNet.Attributes;, and call BenchmarkRunner.Run<BubbleBenchmarks>(); from its Program.cs, after using BenchmarkDotNet.Running;. Let’s run it in Release mode and look at the results:
| Method | Size | Input | Mean | Error | StdDev | |------------------- |------ |------- |-----------------:|----------------:|----------------:| | SortArray | 200 | Random | 21,042.3 ns | 263.63 ns | 233.70 ns | | SortOptimizedArray | 200 | Random | 21,425.5 ns | 295.89 ns | 276.77 ns | | SortArray | 200 | Sorted | 13,062.2 ns | 255.38 ns | 283.86 ns | | SortOptimizedArray | 200 | Sorted | 135.2 ns | 1.71 ns | 1.51 ns | | SortArray | 2000 | Random | 2,639,782.5 ns | 9,167.90 ns | 8,127.10 ns | | SortOptimizedArray | 2000 | Random | 2,900,522.0 ns | 38,752.26 ns | 34,352.87 ns | | SortArray | 2000 | Sorted | 1,168,625.9 ns | 15,326.65 ns | 13,586.68 ns | | SortOptimizedArray | 2000 | Sorted | 1,258.8 ns | 11.85 ns | 10.50 ns | | SortArray | 20000 | Random | 460,066,533.3 ns | 4,037,159.52 ns | 3,776,361.52 ns | | SortOptimizedArray | 20000 | Random | 445,505,646.7 ns | 5,863,502.40 ns | 5,484,723.79 ns | | SortArray | 20000 | Sorted | 116,422,390.9 ns | 671,015.95 ns | 824,067.93 ns | | SortOptimizedArray | 20000 | Sorted | 13,036.4 ns | 130.65 ns | 115.82 ns |
On random numbers, the two methods stay within about 10 percent of each other at every size, and neither one is faster at all of them. The optimized version barely stops early, because the array becomes sorted only near the end of the run, so it does almost all the passes SortArray() does.
On sorted numbers, the early exit pays off. SortOptimizedArray() checks the 20,000 elements once and stops, in about 13 microseconds, while SortArray() runs every pass anyway and needs about 0.12 seconds.
SortArray() is also faster on sorted input than on random input, even though it makes exactly the same number of comparisons. On a sorted array it never swaps, and the if inside the inner loop goes the same way every time, which the processor predicts well.
The table also shows what O(N²) means in practice. Ten times more elements take about a hundred times longer or more: about 2.6 milliseconds for 2,000 random numbers, and about half a second for 20,000.
Conclusion
In this article, we’ve learned how the bubble sort in C# works and how to implement it. It is simple to implement but not that efficient when compared to other algorithms. In case you want to learn how to implement another sorting algorithm, check out this selection sort article.Â
The early exit makes bubble sort fast on arrays that are already sorted, but on random data both versions stay O(N²). For real code, the built-in Array.Sort() is the better choice, and our quicksort article explains what it does under the hood.
Tested with .NET 10.0.10, BenchmarkDotNet 0.15.8 and MSTest 4.5.2.

nice