Question

Consider the problem of sorting an array A[1, ..., n] of integers. We presented an O(n log n)-time algorithm in class and, also, proved a lower bound of Ω(n log n) for any comparison-based algorithm.

3. Give an efficient sorting algorithm for an array D[1, ..., n] whose elements are distinct (D[i] ̸= D[j], for every i ̸= j ∈ {1, ..., n}) and are taken from the set {1, 2, ..., 2n}.

Answer 1

Function sort(A, n)

BEGIN

                temp = create a temporary array of size 2n which store 1 at index I if A contains i

                // array to store sorted array

                ans = [1 .. n]

                // make every entry I temp at index equal to the entry in A to 1

                // traverse te array

                // Time Cmplexity = O( n )

                for i = 1 to n

                BEGIN

                                temp[ A[i] ] = 1

                END

                // traverse the array temp so that we get entries in sorted order

                // if the entry temp[i] = 1, then i was present in A

                // as we traverse in sorted order from 1 to 2n, then the elements(index) which

                // are 1 in temp are in sorted order

                //

                // Time Complexity = O(2n)

                for I = 1 to 2n

                BEGIN

                                // add I to ans

                                ans.add( i )

                END

                return ans

END

Total Time Complexity = O(n) + (2n)

                                         = O(3n)

                                         = O(n)