merge_sort.cpp - master - fluffymax2005/algorithms

merge_sort.cpp
110 строк3 KB
fluffymax2005
Minor code style fix
09 мар 2026, 14:53
09 мар 2026, 14:53856bb59
#include <cstdio>
#include <fstream>
#include <iostream>
#include <new>
#include <ostream>
#include <stdlib.h>

template <typename T> class MergeSort {
public:
  static void sort(T *arr, const size_t length) {
    // Make copy of arr case not enough RAM memory is available
    std::fstream file;
    file.open(bufName, std::ios::in | std::ios::out | std::ios::trunc);
    if (!file.is_open())
      return;

    for (size_t i = 0; i < length; ++i) {
      file << arr[i] << std::endl;
      if (!file.good()) {
        file.close();
        remove(bufName);
        return;
      }
    }
    file.flush();

    try {
      mergeSort(arr, 0, length - 1);
    } catch (const std::bad_alloc &) {
      // Ran out of RAM memory so recover origin createArray
      file.seekg(0);
      for (size_t i = 0; i < length; ++i)
        file >> arr[i];
    }

    file.close();
    remove(bufName);
  }

  static T *createArray(const size_t length) {
    T *arr = new (std::nothrow) T[length];
    if (arr) {
      for (size_t i = 0; i < length; ++i) {
        arr[i] = std::rand() % 65536;
      }
    }

    return arr;
  }

  static void printArray(T *arr, size_t length, std::ostream &os = std::cout) {
    if (arr == nullptr || length < 1)
      return;
    os << "Arr = [";
    for (auto i = 0; i < length; ++i) {
      if (i == length - 1)
        os << arr[i] << "]";
      else
        os << arr[i] << ", ";
    }
  }

private:
  static constexpr const char *bufName = ".tmp-arr";

  static void mergeSort(T *arr, size_t left, size_t right) {
    if (left < right) {
      size_t mid = left + (right - left) / 2;
      mergeSort(arr, left, mid);
      mergeSort(arr, mid + 1, right);

      merge(arr, left, mid, right);
    }
  }

  static void merge(T *arr, size_t left, size_t mid, size_t right) {
    const size_t leftSize = mid - left + 1;
    const size_t rightSize = right - mid;

    T *leftArr = nullptr;
    T *rightArr = nullptr;
    try {
      leftArr = new T[leftSize];
      rightArr = new T[rightSize];
    } catch (const std::bad_alloc &e) {
      delete[] leftArr;
      delete[] rightArr;
      throw e;
    }

    for (size_t i = 0; i < leftSize; ++i)
      leftArr[i] = arr[left + i];
    for (size_t j = 0; j < rightSize; ++j)
      rightArr[j] = arr[mid + j + 1];

    size_t leftIndex = 0, rightIndex = 0, resultIndex = left;

    while (leftIndex < leftSize && rightIndex < rightSize) {
      if (leftArr[leftIndex] <= rightArr[rightIndex])
        arr[resultIndex++] = leftArr[leftIndex++];
      else
        arr[resultIndex++] = rightArr[rightIndex++];
    }

    while (leftIndex < leftSize)
      arr[resultIndex++] = leftArr[leftIndex++];
    while (rightIndex < rightSize)
      arr[resultIndex++] = rightArr[rightIndex++];
  }
};