From Clomosy Docs

(Created page with "The Merge Sort algorithm operates on the divide and conquer principle, working by repeatedly splitting and merging. The array is continuously divided until each element becomes an array of one element. Then, these arrays are merged together in sorted order.<br> You can see a more concrete representation in the diagram below. Steps: *Split the array into two equal parts. *Recursively sort each part using the sorting algorithm. *Merge the sorted subsets. '''Example:'''<...")
 
No edit summary
 
(4 intermediate revisions by one other user not shown)
Line 1: Line 1:
The Merge Sort algorithm operates on the divide and conquer principle, working by repeatedly splitting and merging. The array is continuously divided until each element becomes an array of one element. Then, these arrays are merged together in sorted order.<br>
The Merge Sort algorithm operates on the divide and conquer principle, working by repeatedly splitting and merging. The array is continuously divided until each element becomes an array of one element. Then, these arrays are merged together in sorted order.<br>
You can see a more concrete representation in the diagram below.
You can see a more concrete representation in the diagram below.<br>
 
[[File:MergeSort.mp4|frameless|500px]]<br>


Steps:
Steps:
Line 8: Line 10:
*Merge the sorted subsets.
*Merge the sorted subsets.


'''Example:'''<br>
<b>Example</b><br>


:'''TRObject Syntax'''
<pre>
<pre>
   var
   var
Line 134: Line 135:
</pre>
</pre>


:'''Base Syntax'''
<h2> See Also </h2>
<pre>
  var
    multiArray: array[6] of Integer; // Fixed size main array
    tempArray: array[6] of Integer; // temporary array
    str: string;
    i : Integer;
   
  function Min(a, b: Integer): Integer;
  begin
    if a < b then
      Result := a
    else
      Result := b;
  end;
 
  function Merge(l, m, r: Integer);
  var
    i, j, k: Integer;
  begin
    i := l;
    j := m + 1;
    k := l;
 
    while (i <= m) and (j <= r) do
    begin
      if multiArray[i] <= multiArray[j] then
      begin
        tempArray[k] := multiArray[i];
        Inc(i);
      end
      else
      begin
        tempArray[k] := multiArray[j];
        Inc(j);
      end;
      Inc(k);
    end;
 
    while i <= m do
    begin
      tempArray[k] := multiArray[i];
      Inc(i);
      Inc(k);
    end;
 
    while j <= r do
    begin
      tempArray[k] := multiArray[j];
      Inc(j);
      Inc(k);
    end;
 
    for i := l to r do
    begin
      multiArray[i] := tempArray[i];
    end;
  end;
 
  function IterativeMergeSort(n: Integer);
  var
    curr_size, left_start, mid, right_end: Integer;
  begin
    curr_size := 1;
    while curr_size <= n - 1 do
    begin
      left_start := 0;
      while left_start < n - 1 do
      begin
        mid := Min(left_start + curr_size - 1, n - 1);
        right_end := Min(left_start + 2 * curr_size - 1, n - 1);
 
        Merge(left_start, mid, right_end);
 
        left_start := left_start + 2 * curr_size;
      end;
      curr_size := 2 * curr_size;
    end;
  end;
 
  begin
    // Populate array with initial values
    multiArray[0] := 12;
    multiArray[1] := 11;
    multiArray[2] := 13;
    multiArray[3] := 5;
    multiArray[4] := 1;
    multiArray[5] := 7;
    str := '';
 
    ShowMessage('Unordered array: ');
   
    for i := 0 to Length(multiArray)-2 do
    begin
      str := str + IntToStr(multiArray[i]) + ' ';
    end;
   
    ShowMessage(str);
 
    IterativeMergeSort(Length(multiArray)-1); // Specify array size
 
    str := '';
   
    ShowMessage('Array sorted from smallest to largest: ');
   
    for i := 0 to Length(multiArray)-2 do
    begin
      str := str + IntToStr(multiArray[i]) + ' ';
    end;
    ShowMessage(str);
   
    str := '';
   
    ShowMessage('Array sorted from largest to smallest: ');
   
    for i := Length(multiArray)-2 downto 0 do
    begin
      str := str + IntToStr(multiArray[i]) + ' ';
    end;
    ShowMessage(str);
   
  end;
</pre>
 
 
:'''Output:'''<br>
[[File:BubbleSort.png|frameless|500px]]
 
== See Also ==
* [[Sorting Algorithms]]
* [[Sorting Algorithms]]
* [[TclArray]]
* [[TclArray]]
* [[Arrays]]
* [[Arrays]]
{{#seo:|title=Merge Sort in Clomosy - Clomosy Docs}}
{{#seo:|description=A step-by-step guide to implementing this efficient sorting algorithm for optimal data handling.}}

Latest revision as of 11:03, 23 December 2024

The Merge Sort algorithm operates on the divide and conquer principle, working by repeatedly splitting and merging. The array is continuously divided until each element becomes an array of one element. Then, these arrays are merged together in sorted order.
You can see a more concrete representation in the diagram below.


Steps:

  • Split the array into two equal parts.
  • Recursively sort each part using the sorting algorithm.
  • Merge the sorted subsets.

Example

  var
    multiArray: array[6] of Integer; // Fixed size main array
    tempArray: array[6] of Integer; // temporary array
    str: string;
    i : Integer;
    
  function Min(a, b: Integer): Integer;
  {
    if (a < b)
      Result = a
    else
      Result = b;
  }
  
  function Merge(l, m, r: Integer);
  var
    i, j, k: Integer;
  {
    i = l;
    j = m + 1;
    k = l;
  
    while ((i <= m) && (j <= r))
    {
      if (multiArray[i] <= multiArray[j])
      {
        tempArray[k] = multiArray[i];
        Inc(i);
      }
      else
      {
        tempArray[k] = multiArray[j];
        Inc(j);
      }
      Inc(k);
    }
  
    while (i <= m)
    {
      tempArray[k] = multiArray[i];
      Inc(i);
      Inc(k);
    }
  
    while (j <= r)
    {
      tempArray[k] = multiArray[j];
      Inc(j);
      Inc(k);
    }
  
    for (i = l to r)
    {
      multiArray[i] = tempArray[i];
    }
  }
  
  function IterativeMergeSort(n: Integer);
  var
    curr_size, left_start, mid, right_end: Integer;
  {
    curr_size = 1;
    while (curr_size <= n - 1)
    {
      left_start = 0;
      while (left_start < n - 1)
      {
        mid = Min(left_start + curr_size - 1, n - 1);
        right_end = Min(left_start + 2 * curr_size - 1, n - 1);
  
        Merge(left_start, mid, right_end);
  
        left_start = left_start + 2 * curr_size;
      }
      curr_size = 2 * curr_size;
    }
  }
  
  {
    // Populate array with initial values
    multiArray[0] = 12;
    multiArray[1] = 11;
    multiArray[2] = 13;
    multiArray[3] = 5;
    multiArray[4] = 1;
    multiArray[5] = 7;
    str = '';
  
    ShowMessage('Unordered array: ');
    
    for (i = 0 to Length(multiArray)-2)
    {
      str = str + IntToStr(multiArray[i]) + ' '; 
    }
    
    ShowMessage(str);
  
    IterativeMergeSort(Length(multiArray)-1); // Specify array size
  
    str = '';
    
    ShowMessage('Array sorted from smallest to largest: ');
    
    for (i = 0 to Length(multiArray)-2)
    {
      str = str + IntToStr(multiArray[i]) + ' '; 
    }
    ShowMessage(str);
    
    str = '';
    
    ShowMessage('Array sorted from largest to smallest: ');
    
    for (i = Length(multiArray)-2 downto 0)
    {
      str = str + IntToStr(multiArray[i]) + ' '; 
    }
    ShowMessage(str);
    
  }

See Also

Retrieved from "http:///index.php?title=Merge_Sort&oldid=3446"