Roadmap › Coding Round Practice (DSA in C#) › Module: Sorting, Searching and Recursion
Lessons in this course (14)
11. Sorting algorithms
Intermediate★ Must knowLesson 11 of 14
| Algorithm | Best | Average | Worst | Space | Stable |
|---|---|---|---|---|---|
| Bubble | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Selection | O(n²) | O(n²) | O(n²) | O(1) | No |
| Insertion | O(n) | O(n²) | O(n²) | O(1) | Yes |
| Merge | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes |
| Quick | O(n log n) | O(n log n) | O(n²) | O(log n) | No |
| Heap | O(n log n) | O(n log n) | O(n log n) | O(1) | No |
.NET's Array.Sort/List.Sort use introsort (quicksort + heapsort + insertion sort) — O(n log n) worst case, not stable. LINQ OrderBy is stable.
csharp
// Bubble sort with early exit
static void BubbleSort(int[] a)
{
for (int i = 0; i < a.Length - 1; i++)
{
bool swapped = false;
for (int j = 0; j < a.Length - 1 - i; j++)
if (a[j] > a[j + 1]) { (a[j], a[j + 1]) = (a[j + 1], a[j]); swapped = true; }
if (!swapped) break;
}
}
// Quick sort (Lomuto partition)
static void QuickSort(int[] a, int lo, int hi)
{
if (lo >= hi) return;
int pivot = a[hi], i = lo;
for (int j = lo; j < hi; j++) if (a[j] < pivot) { (a[i], a[j]) = (a[j], a[i]); i++; }
(a[i], a[hi]) = (a[hi], a[i]);
QuickSort(a, lo, i - 1); QuickSort(a, i + 1, hi);
}
// Merge sort
static int[] MergeSort(int[] a)
{
if (a.Length <= 1) return a;
int mid = a.Length / 2;
return Merge(MergeSort(a[..mid]), MergeSort(a[mid..])); // Merge from the arrays lesson
}