Merge Sort Algorithm

by Devansh


Posted on 23 Oct 2018 12:10:14 (1 month ago)




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