Merge Sort

Algorithm

Copy
mergesort(arr, low, high)
Begin
	if (low >= high) return
	Set mid = low + (high - low) / 2
	Call mergesort(arr, low, mid)
	Call mergesort(arr, mid + 1, high)
	
	Declare newArr[high - low + 1];
	Declare i = low
	Declare j = mid + 1
	Declare k = 0
	
	while (i <= mid && j <= high), do
		if (arr[i] <= arr[j]), then
			Set newArr[k] = arr[i];
			Increment i by 1
			Increment k by 1
		else 
			Set newArr[k] = arr[j]
			Increment j by 1
			Increment k by 1
		End If
	End While
	
	while (i <= mid), do
		Set newArr[k] = arr[i]
		Increment k by 1
		Increment i by 1
	End While
	
	while (j <= high), do
		Set newArr[k] = arr[j]
		Increment k by 1
		Increment j by 1
	End While
	
	for (i = 0; i < k; i++), do
		Set arr[low + i] = newArr[i]
	End For
End

Copy
main()
Begin
	Read array size, "size"
	Declare arr[size]
	for (i = 0 i < size; i++), do
		Read number and store in arr[i]
	End For
	Call mergesort(arr, 0, size - 1)
	Display sorted array, arr
End

Program

Copy
#include <stdio.h>

void mergesort(int arr[], int low, int high) {
  if (low >= high) return;

  int mid = low + (high - low) / 2;
  mergesort(arr, low, mid);
  mergesort(arr, mid + 1, high);

  int newArr[high - low + 1];
  int i = low;
  int j = mid + 1;
  int k = 0;

  while (i <= mid && j <= high) {
    if (arr[i] <= arr[j]) newArr[k++] = arr[i++];
    else newArr[k++] = arr[j++];
  } 

  while (i <= mid) newArr[k++] = arr[i++];

  while (j <= high) newArr[k++] = arr[j++];

  for (i = 0; i < k; i++) arr[low + i] = newArr[i];
}

int main() {
  int size;
  printf("Enter array size: ");
  scanf("%d", &size);

  int arr[size];
  printf("Enter array elements: ");
  for (int  i = 0; i < size; i++) scanf("%d", &arr[i]);

  mergesort(arr, 0, size - 1);
  
  printf("Sorted array: ");
  for (int i = 0; i < size; i++) printf("%d ", arr[i]);
}