Heap Sort Implementation in C++ - Incorrect Sorting Order for Large Inputs
I've tried everything I can think of but I'm performance testing and I'm working with an scenario with my Heap Sort implementation in C++... While it works correctly for smaller input sizes, it fails to produce the correct sorting order when I test it with larger arrays (e.g., size 1000 and above). Specifically, the output appears to be partially sorted, and I'm seeing elements out of order as well as duplicate values when there shouldn’t be any. Here’s the code I’ve implemented: ```cpp #include <iostream> #include <vector> using namespace std; void heapify(vector<int>& arr, int n, int i) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left < n && arr[left] > arr[largest]) largest = left; if (right < n && arr[right] > arr[largest]) largest = right; if (largest != i) { swap(arr[i], arr[largest]); heapify(arr, n, largest); } } void heapSort(vector<int>& arr) { int n = arr.size(); for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); for (int i = n - 1; i > 0; i--) { swap(arr[0], arr[i]); heapify(arr, i, 0); } } int main() { vector<int> arr = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1}; // Test with larger input heapSort(arr); for (int i : arr) cout << i << " "; return 0; } ``` I've tested this with smaller arrays and it sorted them correctly, but for larger inputs like a random array of 1000 elements, the output is inconsistent. Here’s the output from my test: ``` 1 2 3 4 5 5 6 6 7 8 9 10 ``` As you can see, there are duplicate values in the output, which shouldn't happen since my input array was unique integers. I've also tried adding print statements in the `heapify` function to debug, but I'm not sure what I'm missing. I suspect it might have to do with how I'm managing the indices or the swap operations. Any insights or suggestions would be greatly appreciated! I'm working on a REST API that needs to handle this. What would be the recommended way to handle this? I'm coming from a different tech stack and learning C++. Thanks for your help in advance!