Two-way merge sort example in C++

input.cpp

#include <iostream>
#include "sort.h"

using namespace std;

int read_array_size() {
  int size;

  cout << "Enter number of elements for sorting, no more than " << MAX_SIZE << endl;
  cin >> size;

  if (size < 1) {
    cerr << "Wrong number of elements, must be positve" << endl;
    exit(1);
  }

  if (size > MAX_SIZE) {
    cerr << "Wrong number of elements, must be less than or equal to " << MAX_SIZE << endl;
    exit(1);
  }

  return size;
}

void read_array(double numbers_list[], int size) {
  cout << "Enter array elements separated by space or carriage return:" << endl;

  for (int i = 0; i < size; i++) {
    cin >> numbers_list[i];
  }
}

void print_array(double numbers_list[], int size) {
  for (int i = 0; i < size; i++) {
    cout << numbers_list[i] << " ";
  }

  cout << endl;
}

input.h

int read_array_size();
void read_array(double[], int);
void print_array(double[], int);

main.cpp

#include <iostream>
#include "input.h"
#include "sort.h"

using namespace std;

int main() {
  int array_size = read_array_size();

  double numbers[array_size];

  read_array(numbers, array_size);

  cout << endl << "Array before sorting:" << endl;

  print_array(numbers, array_size);

  mergesort(numbers, 0, array_size - 1);

  cout << endl << "Array after sorting:" << endl;

  print_array(numbers, array_size);
}

Makefile

CC=g++
CFLAGS=-c -Wall
LDFLAGS=
SOURCES=main.cpp input.cpp sort.cpp
OBJECTS=$(SOURCES:.cpp=.o)
EXECUTABLE=mergesort

all: $(SOURCES) $(EXECUTABLE)

$(EXECUTABLE): $(OBJECTS)
	$(CC) $(LDFLAGS) $(OBJECTS) -o $@

.cpp.o:
	$(CC) $(CFLAGS) $< -o $@

clean:
	rm -rf *.o mergesort

sort.cpp

#include "sort.h"

void mergesort(double array[], int start_index, int end_index) {
  if (start_index >= end_index) {
    return;
  }

  int middle_index = (start_index + end_index) / 2;

  mergesort(array, start_index, middle_index);
  mergesort(array, middle_index + 1, end_index);
  merge(array, start_index, middle_index, end_index);
}

void merge(double array[], int start_index, int middle_index, int end_index) {
  // initial index of left subarray
  int left_index;

  // initial index of right subarray
  int right_index;

  // initial index of merged subarray
  int current_index;

  // size of the left subarray
  int left_chunk_size = middle_index - start_index + 1;

  // size of the right subarray
  int right_chunk_size = end_index - middle_index;

  // make temporary left and right subarrays
  double left_chunk[left_chunk_size];
  double right_chunk[right_chunk_size];

  // initialize subarrays
  for (left_index = 0; left_index < left_chunk_size; left_index++) {
    left_chunk[left_index] = array[start_index + left_index];
  }

  for (right_index = 0; right_index < right_chunk_size; right_index++) {
    right_chunk[right_index] = array[middle_index + right_index + 1];
  }

  left_index = 0;
  right_index = 0;
  current_index = start_index;

  // merge subarrays back into the original array
  while (left_index < left_chunk_size && right_index < right_chunk_size) {
    if (left_chunk[left_index] <= right_chunk[right_index]) {
      array[current_index] = left_chunk[left_index];
      left_index++;
    } else {
      array[current_index] = right_chunk[right_index];
      right_index++;
    }

    current_index++;
  }

  // copy the remaining elements of left subarray, if there are any
  while (left_index < left_chunk_size) {
    array[current_index] = left_chunk[left_index];
    left_index++;
    current_index++;
  }

  // copy the remaining elements of right subarray, if there are any
  while (right_index < right_chunk_size) {
    array[current_index] = right_chunk[right_index];
    right_index++;
    current_index++;
  }
}

sort.h

#ifndef MAX_SIZE
#define MAX_SIZE 100
#endif

void mergesort(double[], int, int);
void merge(double[], int, int, int);