Merge sort is a sorting technique which is based on divide and conquer technique. In this technique array split into two arrays and then again split into two arrays till the point when each array element size is 1.

Then from this point merging came into action and we start merging the sorted arrays.

I am using PHP for this algorithm. Hope you will like this.

function mergeSort(array $arr): array { 
    $len = count($arr);
    $mid = (int) $len / 2;
    if ($len == 1) {
    	return $arr;
    }
    $left  = mergeSort(array_slice($arr, 0, $mid));
    $right = mergeSort(array_slice($arr, $mid));
    return merge($left, $right);
}

function merge(array $left, array $right): array { 
    $combined = []; 
    $countLeft = count($left);
    $countRight = count($right); 
    $leftIndex = $rightIndex = 0; 
    while ($leftIndex < $countLeft && $rightIndex < $countRight) { 
      if ($left[$leftIndex] > $right[$rightIndex]) { 
          $combined[] = $right[$rightIndex]; 
          $rightIndex++; 
      } else { 
          $combined[] = $left[$leftIndex]; 
          $leftIndex++; 
      } 
    } 
    while ($leftIndex < $countLeft) { 
      $combined[] = $left[$leftIndex]; 
      $leftIndex++; 
    } 
    while ($rightIndex < $countRight) { 
      $combined[] = $right[$rightIndex]; 
      $rightIndex++; 
    } 
    return $combined;
}

$arr = [10, 20, 5, 11, 6, 25, 1, 9, 21];
print_r(mergeSort($arr));

Last Modified: 2 years ago