Searching + Sorting Algorithms

• The sequence in which items in a sorted list will be examined in a linear search starts at the beginning of the list and continues until the item is found.
• The sequence in which items in a sorted list will be examined in a binary search starts at the middle of the list. It then repeatedly divides in half the portion of the list that could contain the item, until it has narrowed down the possible locations to just one.
• An advantage of a linear search is that the list does not need to be sorted in order to be searched.
• A disadvantage of a binary search is that the list must be sorted in advance.
• A disadvantage of a linear search is that it can take a long time if the list is very long.
• An advantage of a binary search is that it is faster than a linear search because it eliminates half of the remaining possibilities with each iteration.
• A merge sort is a sorting algorithm that works by breaking down a list into two sublists and then merging them back together.
• An insertion sort is a sorting algorithm that works by inserting the item to be sorted at the beginning of the list.
• A bubble sort is a sorting algorithm that works by repeatedly swapping the elements in a list in order to sort them by comparing an element to the next one.
• An advantage of the merge sort and insertion sort over the bubble sort is that they are more efficient.