Problem 2 (50 points) The following "elegant" sort algorithm gets its name from the Three Stooges slapstick routine in which each stooge hits the other two Hint: this is a bit tricky. Try to elaborate on "what" we know about the contents of each 1/3rd array after each recursive call, with respect to the content of the other two 1/3rd arrays method stoogeSort (a : array, left : int , right : int) if (a[left] > a[right]) I // swap a[left] and a[right] var tmp := a[left]; a[left] :- a[right]; alright] := tmp; if (left+ 1 >- right) return; k := (right - left + 1) div 3; stoogeSort(a,left, right - k); // First two-thirds stoogeSort(a,left + k, right); // Last two-thirds stoogeSort(a,left, right - k); // First two-thirds again (a) What are the appropriate precondition and postcondition for this function? Naturally, we want sort- edness as part of the postcondition! You will submit a text file containing the code with your pre/post- conditions that successfully runs through Dafny. Naturally, this file will include functions, lemmas, and all the extra goodies you require to prove that the function correctly sorts. Like the previous example, the aspect of the proof that the sorted array is a permutation of the original array elements may be skipped as the post condition Problem 2 (50 points) The following "elegant" sort algorithm gets its name from the Three Stooges slapstick routine in which each stooge hits the other two Hint: this is a bit tricky. Try to elaborate on "what" we know about the contents of each 1/3rd array after each recursive call, with respect to the content of the other two 1/3rd arrays method stoogeSort (a : array, left : int , right : int) if (a[left] > a[right]) I // swap a[left] and a[right] var tmp := a[left]; a[left] :- a[right]; alright] := tmp; if (left+ 1 >- right) return; k := (right - left + 1) div 3; stoogeSort(a,left, right - k); // First two-thirds stoogeSort(a,left + k, right); // Last two-thirds stoogeSort(a,left, right - k); // First two-thirds again (a) What are the appropriate precondition and postcondition for this function? Naturally, we want sort- edness as part of the postcondition! You will submit a text file containing the code with your pre/post- conditions that successfully runs through Dafny. Naturally, this file will include functions, lemmas, and all the extra goodies you require to prove that the function correctly sorts. Like the previous example, the aspect of the proof that the sorted array is a permutation of the original array elements may be skipped as the post condition