Note: We will do a bit of run time analysis with sorting, but you will cover this in more depth in COMP122.

For now we will assume that we are going to sort an array of integers. Realize, though, that in C++, you could sort any data type that you want to, as long as you define < and > operators. You are given N pieces of data. Your goal is to return an array of the data in increasing order.

Illustrate each of the below sorts using this data:

p points to arr[1] (p stands for "pass")

repeat

move *p left until it is in its correct position

increment p

until p points to arr[N-1]

**How many passes were done?

**What is the total running time for this algorithm?

build a binary heap of size N

repeat

do a deleteMin() //causes the nodes to come off in sorted order

store each deleted value in another array

until heap is empty

**What is the total running time for this algorithm?

The problem with this approach is that it uses an extra array.

**Why is this a problem?

One way around this problem is to store the deleted value in the last position of the heap. (ie, your heap size is 6, you do a deleteMin(), your heap size becomes 5, and you store the deleted value in arr[5]).

**This is still not perfect. Why not? What could be done to fix the problem?

You are given two arrays of data both of which are already sorted. (Take the above array and break it into two sorted arrays for this example.) Your goal is to merge them into one array.

Actr points to the first element in array A. (One of the little arrays.)

Bctr points to the first element in array B. (The other little array.)

Cctr points to the first element in array C. (Your big array)

(Note: These don't actually have to be pointers. They can just be counters. Either representation is fine.)

Repeat

Compare *Actr and *Bctr.

Write the smallest value in C.

Advance Cctr.

If *Actr was written, advance Actr

Else, advance Bctr.

Until Actr has moved past the end of the array or

Bctr has moved past the end of the array

If Actr has moved past the end of the array, copy the rest of array B to C.

If Bctr has moved past the end of the array, copy the rest of array A to C.

**What is the running time for the above algorithm? Why?

**Now, suppose you are given the original, unsorted array. Write pseudocode for a recursive algorithm to sort this array using the above algorithm.