Professor Abdul-Quader
Merge Sort
There are several options; most involve divide-and-conquer algorithms. Divide-and-conquer means we split the list into smaller parts, and (recursively) sort these smaller lists. There are several ways to do this, we will describe one: the merge sort algorithm.
Implement the merge algorithm. Recall: given an array, sorted from \([start, mid)\) and \([mid, end)\):
Starter code Make sure your method
works by testing the code with the testMerge
method.
Again: the merge sort algorithm works as follows:
On paper: write pseudocode for the merge sort algorithm. (No need to
re-write the merge
method.)
Implement the mergesort algorithm. Then make sure your method works
by testing the code with the testSort
method.
\(n = 8\):
Notice: \(T(1)\) (the base case) is \(O(1)\), and if \(n = 8\), then \(3 = \log_2{8}\).
merge
should take roughly
(end - start)
steps.Questions?
Pseudocode for the game:
currentPlayer = one;
while (game is not over) {
print "The board currently looks like (blah)"
print "Player ???, make a move"
row = currentPlayer.chooseRow(board)
stones = currentPlayer.chooseStones(board, row)
update board
if (currentPlayer == one) {
currentPlayer = two;
} else {
currentPlayer = one;
}
}
current == one
, return “Player One”, otherwise
return “Player Two”print(playerName(currentPlayer) + ": make a move");
After loop:
null
.