procedure Merge_Sort (Values : in out Array_Type) is

   ----------------------------------------------------------------------------
   function Merge (Left  : in Array_Type; 
                   Right : in Array_Type) return Array_Type is
   -- Purpose        : Merge two sorted arrays into a single sorted array.
   -- Preconditions  : Left is sorted. Right is sorted.
   -- Postconditions : A sorted array containing all the elements in Left 
   --                  and Right is returned.
      Left_Index   : Positive;
      Right_Index  : Positive;
      Result_Index : Positive;
      Result       : Array_Type (1 .. Left'Length + Right'Length);
   begin
      -- Initialize array indexes
      Left_Index   := Left'First;
      Right_Index  := Right'First;
      Result_Index := Result'First;
      loop   -- Each iteration one element is moved into Result
         -- Exit when one array is "empty"
         exit when Left_Index  > Left'Last or
                   Right_Index > Right'Last;
         if Left(Left_Index) < Right(Right_Index) then
            Result(Result_Index) := Left(Left_Index);     -- Copy from Left
            Left_Index := Left_Index + 1;
         else
            Result(Result_Index) := Right(Right_Index);   -- Copy from Right
            Right_Index := Right_Index + 1;
         end if;
         Result_Index := Result_Index + 1;
      end loop;

      -- Copy any remaining elements
      if Left_Index <= Left'Last then   -- Still elements remaining in Left?
         Result(Result_Index..Result'Last) := Left(Left_Index..Left'Last);
      else
         Result(Result_Index..Result'Last) := Right(Right_Index..Right'Last);
      end if;
      return Result;
   end Merge;

 --  pragma Inline (Merge);  -- See section on efficiency considerations

   ----------------------------------------------------------------------------
   Middle : Positive;  -- Middle index of array Values
begin
   -- Base Case:  Check for empty array or single element array 
   if Values'Length > 1 then
      Middle := (Values'First + Values'Last) / 2;   -- Divide the array in half
      Merge_Sort (Values(Values'First .. Middle));        -- Sort the left half
      Merge_Sort (Values(Middle + 1 .. Values'Last));     -- Sort the right half
      -- Merge the two sorted halves back into the original array
      Values := Merge (Left  => Values(Values'First .. Middle),
                       Right => Values(Middle + 1 .. Values'Last));
   end if;
end Merge_Sort;