Sorting & Searching

Question 1

Merge Sort (description & runtime)

Answer 1

Time: O(n logn)
Space: depends
Continually halve the array until there are ‘arrays’ of single elements. Then, merge the smaller arrays all the way up until the final result is sorted.
The intuitive way of doing this is to have a helper array per merge that is the size of lefthalf + righthalf. You then iterate over the helper array, continuously picking the result of the comparison operator from either the left or right half. Then increment the index for the half that you chose to take the front of the element from. You could also visualize this merge process utilizing a queue (or stack) of elements, as you’ll pop elements one at a time, knowing they’re already sorted because of the invariant you’re given when you start bottoms-up by merging 2 arrays of size 1.

Question 2

Selection Sort (description & runtime)

Answer 2

Runtime: O(n^2)
Space: O(1) (you modify the array passed as an argument)

This algorithm is also known as the “child’s sort”.

For each position in the array, check all of the elements to the right and find the one that is the smallest (or -est as pertains to your comparison requirement), and swap the smallest into the position at i.

You can make this more efficient in cases where you know a little bit about the array. For example, if you have a deck of cards where each value is guaranteed to appear exactly 4 times, you can do 4 elements at a time rather than 1 element at a time.

Question 3

Bubble Sort (description & runtime)

Answer 3

Runtime: O(n^2)
Space: O(1) (you modify the array passed as an argument)
Do multiple sweeps over the array in which you compare i and i+1 through the entire array. Do a swap if arr[i] and arr[i+1] fail your comparison.
End the loop once there is an iteration in which no swap has been made.

Question 4

Note: This sorting section assumes you are given an array. Why is this an important assumption?

Answer 4

Arrays give you constant time access and should be passed by reference, meaning you can update them and use constant space.

Sorting something like a linked list, stack, queue will not lend themselves necessarily well to these sorts. As an exercise, review these sorts with different collections data structures to see if you can utilize or modify them.

A further challenge is to see if you KNOW the type held within the array/collection, can you use a property of that underlying data structure (think assumptions and all the way down to the bits) that you can use to make a more efficient (be it in space or time) sorting mechanism?

Do you need to use sort to solve your problem? Or is it just the most obvious and intuitive brute force to test against before thinking about something more clever?

Question 5

What are some assumptions to look for when implementing a sort or comparison operator?

Answer 5

• Whether items are unique or not, and what to do in the case of non-unique items.

Question 6

One tip for creative searching

Answer 6

Binary search is usually a goto, but think beyond it! You can leverage different data structures like binary trees and hash tables! Max heaps and tries! You do you!