Given a partially sorted array A of size n, where every t consecutive elements are already sorted, i.e, the subarrays A[1..t], A[(t + 1)..2t], A[(2t + 1)..3t], ..., A[(n - t + 1) ..n] are already sorted, provide the pseudocode that would sort such an array and analyze its running time. Prove a lower bound for sorting such a partially sorted array using a comparison-based sorting algorithm. Does it match the running time of the algorithm?