支持升降序的插入排序处理2000万整数过慢，如何优化？

First off, let's get the elephant in the room out of the way: insertion sort has an O(n²) time complexity, which makes it completely impractical for 20 million elements. Even with optimizations, you're looking at millions of times more operations than an O(n log n) algorithm. But let's break down both quick fixes for your current code, and the real solution you need for large datasets.

Quick Tweaks to Speed Up Your Existing Insertion Sort #

These won't fix the fundamental complexity issue, but they'll reduce overhead and make the code run faster for smaller datasets:

• Swap ArrayList for a primitive array: Using ArrayList.get()/set() adds significant overhead from auto-boxing (if your T is Integer) and bounds checking. Switching to a raw int[] array eliminates this—element access becomes direct and far faster. For example:

  // Replace ArrayList<T> with int[] array
  int elem = array[i]; // Instead of T elem = this.array.get(i)
  

• Move sorting direction checks outside the inner loop: Your current code checks ordinamento == 0 inside the while loop, which runs millions of times. Split the logic into separate loops for ascending and descending to avoid redundant condition checks:

  if (ordinamento == 0) {
      // Ascending sort logic (no inner condition checks)
      for(int i=1; i<array.length; i++){
          int elem = array[i];
          int j=i-1;
          while(j>=0 && array[j] > elem){
              array[j+1] = array[j];
              j--;
          }
          array[j+1] = elem;
      }
  } else {
      // Descending sort logic (no inner condition checks)
      for(int i=1; i<array.length; i++){
          int elem = array[i];
          int j=i-1;
          while(j>=0 && array[j] < elem){
              array[j+1] = array[j];
              j--;
          }
          array[j+1] = elem;
      }
  }
  

• Use binary search to reduce comparisons: Since the left portion of the array is sorted, you can use binary search to find the correct position for the current element (cuts comparisons from O(n) to O(log n) per element). Combine this with System.arraycopy (a native, optimized method) to shift elements faster than manual loops:

  if (ordinamento == 0) {
      for(int i=1; i<array.length; i++){
          int elem = array[i];
          int pos = Arrays.binarySearch(array, 0, i, elem);
          pos = pos < 0 ? -(pos + 1) : pos; // Adjust for not found
          System.arraycopy(array, pos, array, pos+1, i-pos);
          array[pos] = elem;
      }
  }
  

The Real Solution: Switch to an O(n log n) Algorithm #

Insertion sort is only efficient for small datasets (n < 100) or nearly sorted data. For 20 million elements, you need an algorithm with logarithmic time complexity:

• Use Java's built-in Arrays.sort(): This is your best bet. For primitive int[] arrays, it uses a tuned Dual-Pivot Quicksort that's optimized to handle large datasets in seconds. For ascending order, just call:

  Arrays.sort(array);
  

  For descending order, sort ascending first then reverse the array (or use Arrays.sort(array, Collections.reverseOrder()) if working with Integer objects, though primitives are faster).

• Merge Sort: If you need a stable sort (preserves order of equal elements), merge sort is a solid O(n log n) option. It uses O(n) extra space but is reliable for all data types. Java's Arrays.sort(Object[]) uses a variant of merge sort (TimSort, a hybrid of merge and insertion sort) for objects.

• TimSort: This hybrid algorithm (used in Java and Python) combines merge sort with insertion sort for small, sorted "runs"—it's extremely efficient for real-world data that's partially sorted. For primitive arrays, stick with Dual-Pivot Quicksort, but for objects, Arrays.sort() already uses TimSort.

Why Insertion Sort Fails for 20M Elements #

To put the numbers in perspective:

• Insertion sort does ~n²/2 operations. For 20M elements, that's 2e14 operations—even if each operation takes 1 nanosecond, that's ~2.3 days.
• An O(n log n) algorithm like quicksort does ~n log₂(n) operations: 20M * 25 = 5e8 operations, which takes roughly 0.5 seconds (optimistically).

There's no way around it: insertion sort can't handle this size of dataset in a reasonable time. Switching to an O(n log n) algorithm is the only practical solution.

内容的提问来源于stack exchange，提问作者user9039337