Insertion sort stops working after million input

by

Your program is running in O(n²) time, since you have two nested loops that both depend on the size of the input. So once you go from 10,000 to 1,000,000 elements, your program will take 100² = ten thousand times longer to complete. Furthermore, it can be that your dataset fit in the processor’s cache before, but with 1 million elements it no longer does, so this will slow it down even more.

O(n²) algorithms make things go very slow very quickly. With an input size of 10⁶, it means your program will take in the order of 10¹² operations to complete. Assuming your processor runs at a few 10⁹ operations per second at most, and that your algorithm will surely use more than one operation per step, it will take more than 10³ seconds for your program to complete.

More Related Contents:

  1. How to use Quick Sort to sort an array of strings
  2. How to implement classic sorting algorithms in modern C++?
  3. how do you insert the value in a sorted vector?
  4. c++ sort keeping track of indices [duplicate]
  5. How can I sort a std::map first by value, then by key?
  6. The intersection of two sorted arrays
  7. `std::list::sort()` – why the sudden switch to top-down strategy?
  8. How can I sort an STL map by value?
  9. Mixing two arrays by alternating elements two by two
  10. Why does std::getline() skip input after a formatted extraction?
  11. Why would we call cin.clear() and cin.ignore() after reading input?
  12. What’s the most efficient way to erase duplicates and sort a vector?
  13. How to replace all occurrences of a character in string?
  14. Rotating a point about another point (2D)
  15. Sorting a vector in descending order
  16. C++ Efficiently Calculating a Running Median [duplicate]
  17. Multiple inputs on one line
  18. Sorting a std::vector by the string?
  19. Finding nearest point in an efficient way
  20. Issue with cin when spaces are inputted, using string class
  21. Fast n choose k mod p for large n?
  22. Inverting a 4×4 matrix
  23. Print 2-D Array in clockwise expanding spiral from center
  24. std::back_inserter for a std::set?
  25. Get a reverse iterator from a forward iterator without knowing the value type
  26. How to rotate a N x N matrix by 90 degrees? [closed]
  27. How to sort a linked list using bubble-sort?
  28. Mapping elements in 2D upper triangle and lower triangle to linear structure
  29. Fastest way to get the integer part of sqrt(n)?
  30. Finding square root without using sqrt function?

Leave a Comment