Alright — let’s go step by step through the most famous sorting algorithms and I’ll
give you:
1. Idea (how it works)
2. Complexity (time + space)
3. C# Example (clear and easy to follow)
1. Bubble Sort
Idea
• Compare each pair of adjacent elements.
• Swap them if they’re in the wrong order.
• Repeat until no swaps are needed.
Complexity:
• Time: O(n²) worst, O(n) best (already sorted)
• Space: O(1) (in-place)
• Stable:
Example in C#:
using System;
class Program
static void BubbleSort(int[] arr)
int n = arr.Length;
for (int i = 0; i < n - 1; i++)
bool swapped = false;
for (int j = 0; j < n - i - 1; j++)
if (arr[j] > arr[j + 1])
// Swap
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
swapped = true;
// If no swaps, array is sorted
if (!swapped) break;
static void Main()
int[] numbers = { 5, 3, 8, 4, 2 };
BubbleSort(numbers);
Console.WriteLine(string.Join(", ", numbers)); // Output: 2, 3, 4, 5, 8
2. Selection Sort
Idea
• Find the smallest element in the unsorted part.
• Swap it with the first unsorted element.
• Repeat until the array is sorted.
Complexity:
• Time: O(n²) always
• Space: O(1)
• Stable:
Example in C#:
using System;
class Program
static void SelectionSort(int[] arr)
int n = arr.Length;
for (int i = 0; i < n - 1; i++)
int minIndex = i;
for (int j = i + 1; j < n; j++)
if (arr[j] < arr[minIndex])
minIndex = j;
// Swap
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
static void Main()
int[] numbers = { 5, 3, 8, 4, 2 };
SelectionSort(numbers);
Console.WriteLine(string.Join(", ", numbers)); // Output: 2, 3, 4, 5, 8
3. Insertion Sort
Idea
• Take one element at a time and insert it into the correct position in the sorted
part of the array.
• Like sorting cards in your hand.
Complexity:
• Time: O(n²) worst, O(n) best (already sorted)
• Space: O(1)
• Stable:
Example in C#:
using System;
class Program
{
static void InsertionSort(int[] arr)
int n = arr.Length;
for (int i = 1; i < n; i++)
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key)
arr[j + 1] = arr[j];
j--;
arr[j + 1] = key;
static void Main()
int[] numbers = { 5, 3, 8, 4, 2 };
InsertionSort(numbers);
Console.WriteLine(string.Join(", ", numbers)); // Output: 2, 3, 4, 5, 8
4. Merge Sort
Idea
• Divide the array into halves recursively.
• Sort each half.
• Merge the sorted halves.
Complexity:
• Time: O(n log n)
• Space: O(n) (extra arrays during merge)
• Stable:
Example in C#:
using System;
class Program
static void MergeSort(int[] arr, int left, int right)
if (left < right)
int mid = (left + right) / 2;
MergeSort(arr, left, mid);
MergeSort(arr, mid + 1, right);
Merge(arr, left, mid, right);
static void Merge(int[] arr, int left, int mid, int right)
{
int n1 = mid - left + 1;
int n2 = right - mid;
int[] L = new int[n1];
int[] R = new int[n2];
Array.Copy(arr, left, L, 0, n1);
Array.Copy(arr, mid + 1, R, 0, n2);
int i = 0, j = 0, k = left;
while (i < n1 && j < n2)
if (L[i] <= R[j])
arr[k++] = L[i++];
else
arr[k++] = R[j++];
while (i < n1) arr[k++] = L[i++];
while (j < n2) arr[k++] = R[j++];
static void Main()
int[] numbers = { 5, 3, 8, 4, 2 };
MergeSort(numbers, 0, numbers.Length - 1);
Console.WriteLine(string.Join(", ", numbers)); // Output: 2, 3, 4, 5, 8
5. Quick Sort
Idea
• Pick a pivot element.
• Partition array into two halves: smaller than pivot, larger than pivot.
• Recursively sort each half.
Complexity:
• Time: Average O(n log n), Worst O(n²) (rare)
• Space: O(log n) (stack space for recursion)
• Stable:
Example in C#:
using System;
class Program
static 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);
}
}
static int 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++;
(arr[i], arr[j]) = (arr[j], arr[i]);
(arr[i + 1], arr[high]) = (arr[high], arr[i + 1]);
return i + 1;
static void Main()
int[] numbers = { 5, 3, 8, 4, 2 };
QuickSort(numbers, 0, numbers.Length - 1);
Console.WriteLine(string.Join(", ", numbers)); // Output: 2, 3, 4, 5, 8
}
6. Heap Sort
Idea
• Build a max heap.
• Swap the root with the last element.
• Reduce heap size and heapify.
• Repeat until sorted.
Complexity:
• Time: O(n log n)
• Space: O(1)
• Stable:
Example in C#:
using System;
class Program
static void HeapSort(int[] arr)
int n = arr.Length;
// Build heap
for (int i = n / 2 - 1; i >= 0; i--)
Heapify(arr, n, i);
// Extract elements
for (int i = n - 1; i > 0; i--)
{
(arr[0], arr[i]) = (arr[i], arr[0]);
Heapify(arr, i, 0);
static void Heapify(int[] arr, int n, int i)
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i)
(arr[i], arr[largest]) = (arr[largest], arr[i]);
Heapify(arr, n, largest);
static void Main()
{
int[] numbers = { 5, 3, 8, 4, 2 };
HeapSort(numbers);
Console.WriteLine(string.Join(", ", numbers)); // Output: 2, 3, 4, 5, 8
If you want, I can now make a comparison table for all these sorting algorithms
(complexity, stability, best use case) so it’s easy for you to revise before an exam.
That’s the quickest way to remember them.
You said:
yes
ChatGPT said:
Here’s your Sorting Algorithms Comparison Table — designed so you can revise
quickly before an exam
Best
Average Worst
Algorithm Case Space Stable Best Use Case
Time Time
Time
Bubble Teaching basics, tiny
O(n) O(n²) O(n²) O(1)
Sort Yes datasets
Selection Small datasets,
O(n²) O(n²) O(n²) O(1) No
Sort minimal swaps needed
Insertion Nearly sorted data,
O(n) O(n²) O(n²) O(1)
Sort Yes small lists
O(n log Large datasets, stable
Merge Sort O(n log n) O(n log n) O(n)
n) Yes sort needed
O(log General-purpose fast
Quick Sort O(n log n) O(n log n) O(n²) No
n) sorting
Best
Average Worst
Algorithm Case Space Stable Best Use Case
Time Time
Time
O(n log Memory-limited
Heap Sort O(n log n) O(n log n) O(1) No
n) environments
How to Remember Quickly
• O(n²) = slow → Bubble, Selection, Insertion
• O(n log n) = fast → Merge, Quick, Heap
• Stable sorting keeps equal elements in original order → Bubble, Insertion,
Merge
• In-place (low memory) → All except Merge Sort
If you want, I can now make you a similar table for Searching Algorithms so both
topics are complete in one sheet. That way you’ll have all famous search + sort
algorithms together for revision.
You said:
explain the search
ChatGPT said:
Alright — let’s cover searching algorithms the same way we did for sorting:
I’ll explain how each works, give time/space complexity, and provide a C#
example.
1. Linear Search
Idea
• Check each element one by one until the target is found or list ends.
• Works on unsorted data.
Complexity:
• Time: O(n)
• Space: O(1)
• Best for: Small datasets or unsorted data.
Example in C#:
using System;
class Program
static int LinearSearch(int[] arr, int target)
for (int i = 0; i < arr.Length; i++)
if (arr[i] == target)
return i; // Found, return index
return -1; // Not found
static void Main()
int[] numbers = { 5, 3, 8, 4, 2 };
int index = LinearSearch(numbers, 4);
Console.WriteLine(index); // Output: 3
}
2. Binary Search
Idea
• Works only on sorted data.
• Repeatedly divide the search interval in half:
o If target < middle → search left half.
o If target > middle → search right half.
o If equal → found.
Complexity:
• Time: O(log n)
• Space: O(1) (iterative), O(log n) (recursive)
• Best for: Large sorted datasets.
Example in C#:
using System;
class Program
static int BinarySearch(int[] arr, int target)
int left = 0, right = arr.Length - 1;
while (left <= right)
int mid = (left + right) / 2;
if (arr[mid] == target)
return mid;
else if (arr[mid] < target)
left = mid + 1;
else
right = mid - 1;
return -1; // Not found
static void Main()
int[] numbers = { 2, 3, 4, 5, 8 }; // Must be sorted
int index = BinarySearch(numbers, 4);
Console.WriteLine(index); // Output: 2
