Реализация Timsort в C ++ не работает на 10000 номеров

Question

//
//  main.cpp
//  timsort
//
//  Created by Atharva Koli on 2019/1/27.
//  Copyright  © 2019 Atharva Koli. All rights reserved.
//

#include<bits/stdc++.h>

using namespace std;
const int RUN = 32;

// this function sorts array from left index to
// to right index which is of size atmost RUN
void insertionSort(int arr[], int left, int right)
{
    for (int i = left + 1; i <= right; i++)
    {
      int temp = arr[i];
      int j = i - 1;
      while (arr[j] > temp && j >= left)
      {
        arr[j+1] = arr[j];
        j--;
      }
      arr[j+1] = temp;
    }
}

// merge function merges the sorted runs
void merge(int arr[], int l, int m, int r)
{
  // original array is broken in two parts
  // left and right array
  int len1 = m - l + 1, len2 = r - m;
  int left[len1], right[len2];
  for (int i = 0; i < len1; i++)
    left[i] = arr[l + i];
  for (int i = 0; i < len2; i++)
    right[i] = arr[m + 1 + i];

  int i = 0;
  int j = 0;
  int k = l;


  // after comparing, we merge those two array
  // in larger sub array
  while (i < len1 && j < len2)
  {
    if (left[i] <= right[j])
    {
        arr[k] = left[i];
        i++;
    }
    else
    {
        arr[k] = right[j];
        j++;
    }
    k++;
  }

  // copy remaining elements of left, if any
  while (i < len1)
  {
    arr[k] = left[i];
    k++;
    i++;
  }

  // copy remaining element of right, if any
  while (j < len2)
  {
    arr[k] = right[j];
    k++;
    j++;
  }
}

// iterative Timsort function to sort the
// array[0...n-1] (similar to merge sort)
void timSort(int arr[], int n)
{
  // Sort individual subarrays of size RUN
  for (int i = 0; i < n; i+=RUN)
    insertionSort(arr, i, min((i+31), (n-1)));

  // start merging from size RUN (or 32). It will merge
  // to form size 64, then 128, 256 and so on ....
  for (int size = RUN; size < n; size = 2*size)
  {
    // pick starting point of left sub array. We
    // are going to merge arr[left..left+size-1]
    // and arr[left+size, left+2*size-1]
    // After every merge, we increase left by 2*size
    for (int left = 0; left < n; left += 2*size)
    {
        // find ending point of left sub array
        // mid+1 is starting point of right sub array
        int mid = left + size - 1;
        int right = min((left + 2*size - 1), (n-1));

        // merge sub array arr[left.....mid] &
        // arr[mid+1....right]
        merge(arr, left, mid, right);
    }
  }
}

// utility function to print the Array
void printArray(int arr[], int n)
{
  for (int i = 0; i < n; i++)
    printf("%d ", arr[i]);
  printf("\n");
}

// Driver program to test above function
int main()
{
  int arr[] = {"10 thousand numbers separated by commas"};
  int n = sizeof(arr)/sizeof(arr[0]);

  timSort(arr, n);

  printArray(arr, n);
  return 0;
}

Это программа, которую я написал, которая сортирует числа, содержащиеся в массиве, используя алгоритм timsort. Программа скомпилирована и успешно запущена с использованием 100, 1000 ... номеров. Однако, когда я помещаю 10000 или более чисел в массив, программа вылетает, выдавая ошибку компиляции, например: Ошибка компиляции Xcode

Я все еще новичок в программировании на C ++, и приведенный выше код объединен с использованием различных источников в Интернете. Пожалуйста, помогите мне в определении проблемы!

Программа представляет собой стандартную реализацию timsort, эффективно комбинирующую массивы, отсортированные с использованием сортировки вставками.

Answer 1

У вас есть проблема со связью, хотя она не раскрывается мгновенно. Во-первых, вы используете нестандартное расширение VLA внутри merge(), поэтому я не уверен, как эти массивы ведут себя в стеке. Во-вторых, индекс математического слияния приводит к

l,len1 =0,32
l,len1 =64,32
l,len1 =128,32
l,len1 =192,32
...
l,len1 =9472,32
l,len1 =9536,32
l,len1 =9600,32
l,len1 =9664,32
l,len1 =9728,32
l,len1 =9792,32
l,len1 =9856,32
l,len1 =9920,32
l,len1 =9984,32

9984 + 32> 10000, поэтому доступ к arr[l + i] приводит к чтению за концом массива. После нескольких итераций он достигает состояния, в котором это может вызвать ошибку сегментации. Попробуйте напечатать ваши переменные для отладки.