Skip to main content
This type is in `std` namespace
Source Link
Toby Speight
  • 81.7k
  • 14
  • 101
  • 308
  • Using int for indexing is wrong. Use std::size_t.

  • An addition in int q = (p + r) / 2; may overflow. Consider

      int q = p + (r - p)/2;
    
  • A single most important advantage of merge sort is stability: element compare equal retain their original order. In your implementation

      if(left_sub[i] < right_sub[j])
    

    stability is lost: of the two equals the one from the right is merged first. It doesn't really matter for integers, but still

      if(left_sub[i] <= right_sub[j])
    

    is a correct way.

  • As the partitions get smaller and smaller, a recursion overhead of quick sort becomes more and more expensive. Do not recurse into small partitions; have a final pass of an insertion sort instead, like in:

    void quick_sort_helper(int* arr, int low, int high) {
      if (low + CUTOFF < high) {
        int partition_index = partition(arr, low, high); // partition the array and get the partition index
        quick_sort_helper(arr, low, partition_index - 1); // recursively sort the left subarray
        quick_sort_helper(arr, partition_index + 1, high); // recursively sort the right subarray
      }
    }
    
    void quick_sort(int* arr, int size) {
      quick_sort_helper(arr, 0, size - 1);
      insertion_sort(arr, 0, size - 1);
    }
    

    Selection of a cutoff value is an interesting question. Insertion sorting an arbitrary array has a quadratic time complexity; however we are guaranteed that by the time insertion_sort is called, the array is almost sorted. Every element is within a CUTOFF of its final destination. The time complexity becomes O(n * CUTOFF). Since we are striving to obtain an O(N * log n) complexity, log n is a natural choice.

    That said, most implementation use a cutoff constant like 16 or 32.

  • Using int for indexing is wrong. Use size_t.

  • An addition in int q = (p + r) / 2; may overflow. Consider

      int q = p + (r - p)/2;
    
  • A single most important advantage of merge sort is stability: element compare equal retain their original order. In your implementation

      if(left_sub[i] < right_sub[j])
    

    stability is lost: of the two equals the one from the right is merged first. It doesn't really matter for integers, but still

      if(left_sub[i] <= right_sub[j])
    

    is a correct way.

  • As the partitions get smaller and smaller, a recursion overhead of quick sort becomes more and more expensive. Do not recurse into small partitions; have a final pass of an insertion sort instead, like in:

    void quick_sort_helper(int* arr, int low, int high) {
      if (low + CUTOFF < high) {
        int partition_index = partition(arr, low, high); // partition the array and get the partition index
        quick_sort_helper(arr, low, partition_index - 1); // recursively sort the left subarray
        quick_sort_helper(arr, partition_index + 1, high); // recursively sort the right subarray
      }
    }
    
    void quick_sort(int* arr, int size) {
      quick_sort_helper(arr, 0, size - 1);
      insertion_sort(arr, 0, size - 1);
    }
    

    Selection of a cutoff value is an interesting question. Insertion sorting an arbitrary array has a quadratic time complexity; however we are guaranteed that by the time insertion_sort is called, the array is almost sorted. Every element is within a CUTOFF of its final destination. The time complexity becomes O(n * CUTOFF). Since we are striving to obtain an O(N * log n) complexity, log n is a natural choice.

    That said, most implementation use a cutoff constant like 16 or 32.

  • Using int for indexing is wrong. Use std::size_t.

  • An addition in int q = (p + r) / 2; may overflow. Consider

      int q = p + (r - p)/2;
    
  • A single most important advantage of merge sort is stability: element compare equal retain their original order. In your implementation

      if(left_sub[i] < right_sub[j])
    

    stability is lost: of the two equals the one from the right is merged first. It doesn't really matter for integers, but still

      if(left_sub[i] <= right_sub[j])
    

    is a correct way.

  • As the partitions get smaller and smaller, a recursion overhead of quick sort becomes more and more expensive. Do not recurse into small partitions; have a final pass of an insertion sort instead, like in:

    void quick_sort_helper(int* arr, int low, int high) {
      if (low + CUTOFF < high) {
        int partition_index = partition(arr, low, high); // partition the array and get the partition index
        quick_sort_helper(arr, low, partition_index - 1); // recursively sort the left subarray
        quick_sort_helper(arr, partition_index + 1, high); // recursively sort the right subarray
      }
    }
    
    void quick_sort(int* arr, int size) {
      quick_sort_helper(arr, 0, size - 1);
      insertion_sort(arr, 0, size - 1);
    }
    

    Selection of a cutoff value is an interesting question. Insertion sorting an arbitrary array has a quadratic time complexity; however we are guaranteed that by the time insertion_sort is called, the array is almost sorted. Every element is within a CUTOFF of its final destination. The time complexity becomes O(n * CUTOFF). Since we are striving to obtain an O(N * log n) complexity, log n is a natural choice.

    That said, most implementation use a cutoff constant like 16 or 32.

Source Link
vnp
  • 57.3k
  • 4
  • 51
  • 140

  • Using int for indexing is wrong. Use size_t.

  • An addition in int q = (p + r) / 2; may overflow. Consider

      int q = p + (r - p)/2;
    
  • A single most important advantage of merge sort is stability: element compare equal retain their original order. In your implementation

      if(left_sub[i] < right_sub[j])
    

    stability is lost: of the two equals the one from the right is merged first. It doesn't really matter for integers, but still

      if(left_sub[i] <= right_sub[j])
    

    is a correct way.

  • As the partitions get smaller and smaller, a recursion overhead of quick sort becomes more and more expensive. Do not recurse into small partitions; have a final pass of an insertion sort instead, like in:

    void quick_sort_helper(int* arr, int low, int high) {
      if (low + CUTOFF < high) {
        int partition_index = partition(arr, low, high); // partition the array and get the partition index
        quick_sort_helper(arr, low, partition_index - 1); // recursively sort the left subarray
        quick_sort_helper(arr, partition_index + 1, high); // recursively sort the right subarray
      }
    }
    
    void quick_sort(int* arr, int size) {
      quick_sort_helper(arr, 0, size - 1);
      insertion_sort(arr, 0, size - 1);
    }
    

    Selection of a cutoff value is an interesting question. Insertion sorting an arbitrary array has a quadratic time complexity; however we are guaranteed that by the time insertion_sort is called, the array is almost sorted. Every element is within a CUTOFF of its final destination. The time complexity becomes O(n * CUTOFF). Since we are striving to obtain an O(N * log n) complexity, log n is a natural choice.

    That said, most implementation use a cutoff constant like 16 or 32.