-- add put statements to procedure Split every time Left and Right change to show how the
-- sort is working.
procedure Quick_Sort (Values : in out Array_Type) is

   ----------------------------------------------------------------------------
   procedure Swap (Left : in out Element_Type; Right : in out Element_Type) is
   -- Swaps the values of two variables
      Temp : Element_Type;
   begin      Temp  := Left;
      Left  := Right;
      Right := Temp;
   end Swap;

   ----------------------------------------------------------------------------
   function ">=" (Left : in Element_Type; Right : in Element_Type) 
                  return Boolean is
   begin
      return not (Left < Right);
   end ">=";

   ----------------------------------------------------------------------------
   procedure Split (Values      : in out Array_Type;
                    Split_Index :    out Positive) is
      Left  : Positive;
      Right : Positive;
   begin 
      Left  := Values'First + 1;
      Right := Values'Last;
      Ada.integer_text_io.put (Left, Right);
		ada.text_io.new_line;
      loop  -- Each iteration, two out of place values are swapped
         -- Left to right search
         loop  -- Each iteration on element is inspected
            -- Exit when searches cross or find an element on wrong side
            exit when Left > Right  or else 
                      Values(Left) >= Values(Values'First);
            Left := Left + 1;
         end loop;
         -- Right to left search
         loop  -- Each iteration on element is inspected
            -- Exit when searches cross or find an element on wrong side
            exit when Left > Right  or  
                      Values(Right) < Values(Values'First);
            Right := Right - 1;
         end loop;
         -- Exit outer loop when searches cross
         exit when Left > Right;
         -- Swap the two values on the wrong side of the split value
         Swap (Values(Left), Values(Right));
         Left  := Left  + 1;
         Right := Right - 1;
      end loop;
      -- Move the split value into its proper location
      Swap (Values(Values'First), Values(Right));
      -- Return the index of the value that divides the two portions
      Split_Index := Right;
   end Split;

--   pragma Inline (Swap, ">=", Split); -- See section on efficiency

   ----------------------------------------------------------------------------
   Split_Index : Positive;
begin
   if Values'Length > 1 then
      Split (Values, Split_Index);
      Quick_Sort (Values(Values'First .. Split_Index - 1));
      Quick_Sort (Values(Split_Index + 1 .. Values'Last));
   end if;
end Quick_Sort;