Searching involves determining if a search key is present in the data and, if so, finding its location.

Sorting involves arranging data in order.

The linear search algorithm searches an array’s elements sequentially until it finds one that matches the search key. If the search key is not in the array, the algorithm tests every element and returns an indication (such as a sentinel value) that the search key was not found.

One way to describe the efficiency of an algorithm is with Big O notation (O), which indicates how hard an algorithm may have to work to solve a problem.

In searching and sorting algorithms, Big O is dependent on how many elements are in the data.

An $O\left(n\right)$ algorithm is referred to as having a linear runtime.

Big O is designed to highlight dominant factors and ignore terms that become unimportant with high n values. Big O notation is concerned with the growth rate of algorithm runtimes, so constants are ignored.

The linear search algorithm runs in $O\left(n\right)$ time.

The worst case in linear search is that every element must be checked to determine whether the search item exists. This occurs if the search key is the last element in the array or is not present.

The binary search algorithm is more efficient than the linear search algorithm, but it requires that the array be sorted.

The first iteration of binary search tests the middle array element. If this is the search key, the algorithm returns its location. If the search key is less than the middle element, the search continues with the array’s first half. If the search key is greater than the middle element, the search continues with the array’s second half. Each iteration of binary search tests the middle value of the remaining array and, if the element is not found, eliminates half of the remaining elements.

Binary search is a more efficient searching algorithm than linear search because with each comparison it eliminates from consideration half of the elements in the array.

Binary search runs in $O\left(\text{log }n\right)$ time, because each step removes half of the remaining elements.

The selection sort is a simple, but inefficient, sorting algorithm.

The first iteration of the selection sort selects the smallest element in the array and swaps it with the first element. The second iteration selects the second-smallest element (which is the smallest remaining element) and swaps it with the second element. Selection sort continues until the largest element is in the last position. After the ith iteration of selection sort, the smallest i elements of the whole array are sorted into the first i positions.

The selection sort algorithm runs in $O\left(n^2\right)$ time.

The first iteration of insertion sort takes the second element in the array and, if it’s less than the first, swaps them. The second iteration looks at the third element and inserts it in the correct position with respect to the first two. After the ith iteration of insertion sort, the first i elements in the original array are sorted.

The insertion sort algorithm runs in $O\left(n^2\right)$ time.

Merge sort is a sorting algorithm that is faster, but more complex to implement, than selection sort and insertion sort.

The merge sort algorithm sorts an array by splitting it into two equal-sized subarrays, sorting each recursively and merging them into one larger array.

Merge sort’s base case is an array with one element. A one-element array is already sorted.

Merge sort performs the merge by looking at the first element in each array, which is also the smallest. Merge sort takes the smallest of these and places it in the first element of the larger array. If there are still elements in the subarray, merge sort looks at the second element in that subarray (which is now the smallest element remaining) and compares it to the first element in the other subarray. Merge sort continues this process until the larger array is filled.

In the worst case, the first call to merge sort has to make $O\left(n\right)$ comparisons to fill the n slots in the final array.

The merging portion of the merge sort algorithm is performed on two subarrays, each of approximately size $n/2$. Creating each of these subarrays requires $n\mathrm{/}2-1$ comparisons for each subarray, or $O\left(n\right)$ comparisons total. This pattern continues as each level works on twice as many arrays, but each is half the size of the previous array. Similar to binary search, this halving results in log n levels for a total efficiency of $O\left(n\text{ log }n\right)$.