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

  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

• Sorting Algorithms
• TclArray
• Arrays