How to resolve the algorithm Sorting algorithms/Merge sort step by step in the Ada programming language

Published on 12 May 2024 09:40 PM
#Ada

How to resolve the algorithm Sorting algorithms/Merge sort step by step in the Ada programming language

Table of Contents

Problem Statement

The   merge sort   is a recursive sort of order   nlog(n). It is notable for having a worst case and average complexity of   O(nlog(n)),   and a best case complexity of   O(n)   (for pre-sorted input). The basic idea is to split the collection into smaller groups by halving it until the groups only have one element or no elements   (which are both entirely sorted groups). Then merge the groups back together so that their elements are in order. This is how the algorithm gets its   divide and conquer   description.

Write a function to sort a collection of integers using the merge sort.

The merge sort algorithm comes in two parts: The functions in pseudocode look like this:

Note:   better performance can be expected if, rather than recursing until   length(m) ≤ 1,   an insertion sort is used for   length(m)   smaller than some threshold larger than   1.   However, this complicates the example code, so it is not shown here.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Sorting algorithms/Merge sort step by step in the Ada programming language

Source code in the ada programming language

generic
   type Element_Type is private;
   type Index_Type is (<>);
   type Collection_Type is array(Index_Type range <>) of Element_Type;
   with function "<"(Left, Right : Element_Type) return Boolean is <>;

package Mergesort is
   function Sort(Item : Collection_Type) return Collection_Type;
end MergeSort;


package body Mergesort is
   
   -----------
   -- Merge --
   -----------
   
   function Merge(Left, Right : Collection_Type) return Collection_Type is
      Result : Collection_Type(Left'First..Right'Last);
      Left_Index : Index_Type := Left'First;
      Right_Index : Index_Type := Right'First;
      Result_Index : Index_Type := Result'First;
   begin
      while Left_Index <= Left'Last and Right_Index <= Right'Last loop
         if Left(Left_Index) <= Right(Right_Index) then
            Result(Result_Index) := Left(Left_Index);
            Left_Index := Index_Type'Succ(Left_Index); -- increment Left_Index
         else
            Result(Result_Index) := Right(Right_Index);
            Right_Index := Index_Type'Succ(Right_Index); -- increment Right_Index
         end if;
         Result_Index := Index_Type'Succ(Result_Index); -- increment Result_Index
      end loop;
      if Left_Index <= Left'Last then
         Result(Result_Index..Result'Last) := Left(Left_Index..Left'Last);
      end if;
      if Right_Index <= Right'Last then
         Result(Result_Index..Result'Last) := Right(Right_Index..Right'Last);
      end if;
      return Result;
   end Merge;
   
   ----------
   -- Sort --
   ----------

   function Sort (Item : Collection_Type) return Collection_Type is
      Result : Collection_Type(Item'range);
      Middle : Index_Type;
   begin
      if Item'Length <= 1 then
         return Item;
      else
         Middle := Index_Type'Val((Item'Length / 2) + Index_Type'Pos(Item'First));
         declare
            Left : Collection_Type(Item'First..Index_Type'Pred(Middle));
            Right : Collection_Type(Middle..Item'Last);
         begin
            for I in Left'range loop
               Left(I) := Item(I);
            end loop;
            for I in Right'range loop
               Right(I) := Item(I);
            end loop;
            Left := Sort(Left);
            Right := Sort(Right);
            Result := Merge(Left, Right);
         end;
         return Result;
      end if;
   end Sort;

end Mergesort;


with Ada.Text_Io; use Ada.Text_Io;
with Mergesort; 

procedure Mergesort_Test is
   type List_Type is array(Positive range <>) of Integer;
   package List_Sort is new Mergesort(Integer, Positive, List_Type);
   procedure Print(Item : List_Type) is
   begin
      for I in Item'range loop
         Put(Integer'Image(Item(I)));
      end loop;
      New_Line;
   end Print;
   
   List : List_Type := (1, 5, 2, 7, 3, 9, 4, 6);
begin
   Print(List);
   Print(List_Sort.Sort(List));
end Mergesort_Test;

You may also check:How to resolve the algorithm Determine if a string is numeric step by step in the Zoea Visual programming language
You may also check:How to resolve the algorithm Department numbers step by step in the Phix programming language
You may also check:How to resolve the algorithm Calculating the value of e step by step in the Standard ML programming language
You may also check:How to resolve the algorithm Ray-casting algorithm step by step in the Raku programming language
You may also check:How to resolve the algorithm Run-length encoding step by step in the sed programming language