Let us consider an array a[1...n] with integer values (both positive and negative). Choose three different sorting methods to sort increasingly the array. Which sorting method is the fastest (from the three chosen methods)? Analyze the complexity (problem size, dominant operation and complexity) of the three algorithms in order to prove your answer. (1p) Now that your array a[1...n] is sorted increasingly, consider a value v and using an algorithm with complexity 0(lgn), determine the position where this value can be inserted such that the array remains increasingly sorted. Prove the total correctness of your algorithm (use an invariant). (1p)

Consider another increasingly sorted array b[1...m]. So now you have a[1...n] and b[1...m] with elements not necessarily distinct.

a. Construct a strictly increasingly sorted array with the distinct elements from a and b. Analyze the complexity (problem size, dominant operation and complexity) of your algorithm. (0.5p)

b. Propose an algorithm with linear complexity to determine the set with common elements of the two arrays a and b. Analyze the complexity (problem size, dominant operation and complexity) of your algorithm. (0.5p)

Indications:

All the algorithms will be written in pseudocode.