Thread: Need help on this bitonic merge sort

  1. #1
    Registered User
    Join Date
    Aug 2022
    Posts
    6

    Need help on this bitonic merge sort

    So for my assignment I need to implement a recursive bitonic mergesort that takes the input array, size, output array, and output_asc where true ascends and false descends.
    There is a helper function in the test runner so I don't need to allocate extra memory for the left half and right half so I'm lost in the recursion when calling mergesort for left half and right half.
    Can someone check my code to see what I'm doing wrong?

    Code:
    #include<iostream>
    void merge(int *input, int size, int *output, bool output_asc)
    {
      int mid = size / 2;
      int i = 0;
      int j = size - 1;
      int k = 0;
    
      if (output_asc) {
        while (i < mid && j >= mid) {
          if (input <= input[j])
            output[k++] = input[i++];
          else
            output[k++] = input[j--];
        }
      } else {
        while (i < mid && j >= mid) {
          if (input >= input[j])
            output[k++] = input[i++];
          else
            output[k++] = input[j--];
        }
      }
    
      // Copy the remaining elements from the first section
      while (i < mid) {
        output[k++] = input[i++];
      }
    
      // Copy the remaining elements from the second section
      while (j >= mid) {
        output[k++] = input[j--];
      }
    }
    
    void mergesort(int *input, int size, int *output, bool output_asc)
    {
      if (size == 0)
        return;
      else if (size == 1) {
        output[0] = input[0];
      } else {
        int mid = size / 2;
        mergesort(input, mid, output, true);
        mergesort(input + mid, size - mid, output + mid, false);
    
        for (int i = 0; i < size; ++i)
          input = output;
    
        merge(input, size, output, output_asc);
      }
    }
    
    int main()
    {
      // Example usage
      const int size = 8;
      int input = { 4, 2, 7, 1, 5, 8, 3, 6 };
      int output;
    
      // Ascending order
      mergesort(input, size, output, true);
      std::cout << "Sorted in ascending order: ";
      for (int i = 0; i < size; i++) {
        std::cout << output << " ";
      }
      std::cout << std::endl;
    
      // Descending order
      mergesort(input, size, output, false);
      std::cout << "Sorted in descending order: ";
      for (int i = 0; i < size; i++) {
        std::cout << output << " ";
      }
      std::cout << std::endl;
    
      return 0;
    
    }
    Last edited by Salem; 11-21-2023 at 02:13 PM. Reason: crayola removed

  2. #2
    Registered User
    Join Date
    Dec 2017
    Posts
    1,626
    Firstly, when you paste code, you need to paste it as plain text, not text with a bunch of formatting in it.

    As for your problem, instead of this:
    Code:
            mergesort(input,       mid,        output,       true);
            mergesort(input + mid, size - mid, output + mid, false);
    try this:
    Code:
            mergesort(input,       mid,        output,        output_asc);
            mergesort(input + mid, size - mid, output + mid, !output_asc);
    A little inaccuracy saves tons of explanation. - H.H. Munro

  3. #3
    Registered User
    Join Date
    Aug 2022
    Posts
    6
    Quote Originally Posted by john.c View Post
    Firstly, when you paste code, you need to paste it as plain text, not text with a bunch of formatting in it.

    try this:
    Code:
            mergesort(input,       mid,        output,        output_asc);
            mergesort(input + mid, size - mid, output + mid, !output_asc);
    Gotcha will do for next time! And thank you sir... My brain was going crazy trying to fix this and that one line was it....

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Merge sort fails to sort
    By Cresh07 in forum C++ Programming
    Replies: 3
    Last Post: 09-23-2009, 11:17 AM
  2. Quick Sort or Merge Sort???
    By swanley007 in forum C++ Programming
    Replies: 6
    Last Post: 11-10-2005, 06:48 PM
  3. Merge Sort
    By osal in forum C++ Programming
    Replies: 3
    Last Post: 06-05-2005, 12:31 PM
  4. Quick sort VS Merge Sort
    By sachitha in forum Tech Board
    Replies: 7
    Last Post: 09-03-2004, 11:57 PM
  5. merge sort and selection sort and time spent on both
    By misswaleleia in forum C Programming
    Replies: 3
    Last Post: 06-04-2003, 02:24 PM

Tags for this Thread