Annoucements #

First assignment open

Mergesort cont. #

Solution to last exercise:

The first sort method:

• space complexity is O(n)
• running time is

The second method

• space complexity is O(1)
• running time is O(nlog(n))

An example of a stable sorting algorithm:

Unsorted: [3(1), 2, 1, 5, 3(2)] (where the (1) indicates that it is the first 3 in the array)

Sorted: [1, 2, 3(1), 3(2), 5] this is stable [1, 2, 3(2), 3(1), 5] this is unstable

For example if you have two arrays: [1, 3, 5] and [7, 9, 11] you can check the last element of the first array against the first element of the second, you can skip the merge.

Quick sort #