Sorting and searching

.NET has built-in sorting methods: Array.Sort(), List<T>.Sort() and LINQ OrderBy(). They are highly optimized, often using introspective sort, a hybrid of QuickSort, HeapSort and InsertionSort. Even so, it’s beneficial to understand the principles and complexities of the common algorithms. The notation is in the Big O noteBig O notationHow run time or memory grows as the input grows.Opens in a new tab.

Sorting algorithms

Algorithm	Complexity	Notes
Bubble sort	O(n²)	Simple but inefficient for large datasets.
Insertion sort	O(n²)	Efficient for small or nearly sorted datasets.
Merge sort	O(n log n)	Divide and conquer, stable, good worst-case performance. Requires extra space.
Quick sort	O(n log n) average case, O(n²) worst case	In-place (low space complexity). Often faster in practice than merge sort.

Searching algorithms

Algorithm	Complexity	Notes
Linear search	O(n)	Iterates through the collection one by one. Works on unsorted data.
Binary search	O(log n)	Requires the collection to be sorted. Efficiently finds an item by repeatedly dividing the search interval in half.