Sort an array whose first n-sqrt(n) elements are already sorted - Interview technical questions and solutions in C#

Sort an array whose first n-sqrt(n) elements are already sorted - Interview technical questions and solutions in C#

Design an algorithm to sort an array whose first n-sqrt(n) elements are already sorted. What is the complexity of the algorithm.

Solution

1. Sort last sqrt(n) elements

2. Merge sort

Complexity is n + sqrt(n) * log(sqrt(n)

        static void SortN_SqrtN(int[] arr)

        {

            if (arr.Length < 2) return;

            int unsortedLen = (int)Math.Sqrt(arr.Length);          

            // Quick sort

            Array.Sort(arr, arr.Length - unsortedLen, unsortedLen);        

            

            int[] subArray = new int[unsortedLen];

            Array.Copy(arr, arr.Length - unsortedLen, subArray, 0, unsortedLen);

            

            // Merge sort

            int k = arr.Length - 1;

            int i = arr.Length - unsortedLen - 1;

            int j = subArray.Length - 1;

            while (i >= 0 && j >= 0)

            {

                if (arr[i] >= subArray[j])

                {

                    arr[k--] = arr[i--];

                }

                else

                {

                    arr[k--] = subArray[j--];

                }

            }

            while (j >= 0)

            {

                arr[k--] = subArray[j--];

            }        

        }

http://www.careercup.com/question?id=10176906
Read full article from Sort an array whose first n-sqrt(n) elements are already sorted - Interview technical questions and solutions in C#