Sorting and Searches

Curated by James Ding Last modified: Sep 30, 2026 2 min read

Sorting and searching are two of the most common operations in computer science. Sorting is the process of arranging elements in a specific order, while searching is the process of finding a specific element in a collection of elements.

Sorts

Bubble Sort

Bubbles elements to the top of the list by comparing adjacent elements and swapping them if they are in the wrong order.

Worst Case Time Complexity: $O (N^{2})$
Best Case Time Complexity: $Ω (N)$

Selection Sort

Selects the smallest element from the unsorted portion of the list and swaps it with the first unsorted element.

Worst Case Time Complexity: $O (N^{2})$
Best Case Time Complexity: $Ω (N^{2})$
Tight Bound Time Complexity: $Θ (N^{2})$

Insertion Sort

Builds the sorted list one element at a time by inserting elements into their correct position.

Worst Case Time Complexity: $O (N^{2})$
Best Case Time Complexity: $Ω (N)$

Merge Sort

Divides the list into smaller sublists, sorts the sublists, and then merges them back together.

Worst Case Time Complexity: $O (N lo g N)$
Best Case Time Complexity: $Ω (N lo g N)$

Quick Sort

Divides the list into smaller sublists based on a pivot element, sorts the sublists, and then combines them.

Worst Case Time Complexity: $O (N^{2})$
Best Case Time Complexity: $Ω (N lo g N)$

Searches

Linear Search

Searches for an element by checking each element in the list sequentially.

Worst Case Time Complexity: $O (N)$
Best Case Time Complexity: $Ω (1)$

Binary Search

Given a sorted array, searches for an element in a sorted list by repeatedly dividing the search interval in half.

Worst Case Time Complexity: $O (lo g N)$
Best Case Time Complexity: $Ω (1)$

Detailed implementations

Source

The existing course note was retained and normalized during the merge.