Merge Sort

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
TRObject Syntax

  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);
    
  }

Base Syntax

  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;

See Also

• Sorting Algorithms
• TclArray
• Arrays