Binary search is used to go through an array efficiently—but, binary search only works when the array is sorted.
So how do you go about sorting an array of values?
Here’s the short answer: there are many sorting types, and deciding which method to use depends on the situation.
To get into more detail, we are going to look at three different sorting algorithms:
- Insertion sort
- Merge sort
- Selection Sort
Selection sort
Selection sort is the most basic type of sort; the algorithm repeatedly finds the smallest value from the unsorted subarray and moves it to a sorted subarray in the beginning of the array.
Learn more: Algorithms for kids
(A subarray is part of an array. There will be two subarrays: the portion that's sorted and the remaining that's unsorted.)
Take the following array example:
Initially, the smallest value is set to the value in the starting index (“5”). When the whole array is traversed, and the smallest value (“1”) is found, swap the smallest value with the value in the starting index. Repeat the process for the next value and keep repeating until you’ve traversed the entire array.
When you need something quickly, selection sort is easy to implement, though it’s not that efficient.
Insertion Sort
On the other hand, insertion sort finds subsequent values and sorts them. So, you’d use insertion sort to rearrange an unsorted array from smallest to largest number.
Imagine you’re being dealt a hand of cards one by one. To help organize the cards, you begin sorting the dealt cards with the smallest value in the beginning.
Given your current unsorted hand, how would you begin sorting your cards? Insertion sort is similar to how you'd organize this hand of cards.
Start with the first card in your hand. There is no card to its left, so it stays. The second card is now the key and is compared to the card on its left. Since 4 is greater, 4 is moved one spot ahead. Since there is no card to compare the key to, it is inserted into that spot.
Again, the difference here is that selection sort continuously finds the smallest value, while insertion sort finds subsequent values and sorts them.
Merge Sort
Last, merge sort is a divide and conquer algorithm that keeps dividing the array into halves until the divided subarrays consist of one element. From there, it merges the halves back together while sorting the values as it merges.
To achieve this outcome, you need recursion, which is a programming technique in which a method calls itself. It's often used when a problem can be solved by dividing it into subproblems that in turn use the same technique to solve them.
A base case returns a value without making any more recursive calls. A method that calls itself won't continue running the rest of its code until the method called returns a value.
For example, let’s say that at a party, you want to order pizza for you and your friends. But you'll only get pizza if your friend gets pizza and your friend will only get pizza if their friend gets pizza. This continues until one friend says enough is enough and just says yes. This "yes" is then passed back up from friend to friend to friend to you.
This flow of information is similar to how recursion works in code. A recursive method keeps calling itself until an answer is found. Each person represents one call to itself. A method will keep calling itself until the base case is reached. In this example, the base case is the first "Yes!" and is returned back to the first call.
When you need a stable sort or you need to sort a large data set, this is a great option. It’s efficient; however, it takes up a lot of space and isn’t easy to implement. Merge sort is also useful for sorting linked lists.