/* Write a Java program to create an interface Sortable with a method sort (int[] array) that sorts an array of integers in descending order. Create two classes QuickSort and MergeSort that implement the Sortable interface and provide their own implementations of the sort() method. */
              interface Sortable {
                  void sort(int[] array);
              }
              
              class QuickSort implements Sortable {
                  
                  public void sort(int[] array) {
                      quickSort(array, 0, array.length - 1);
                  }
              
                  private void quickSort(int[] array, int low, int high) {
                      if (low < high) {
                          int pivotIndex = partition(array, low, high);
                          quickSort(array, low, pivotIndex - 1);
                          quickSort(array, pivotIndex + 1, high);
                      }
                  }
              
                  private int partition(int[] array, int low, int high) {
                      int pivot = array[high];
                      int i = low - 1;
              
                      for (int j = low; j < high; j++) {
                          if (array[j] >= pivot) {
                              i++;
                              swap(array, i, j);
                          }
                      }
              
                      swap(array, i + 1, high);
                      return i + 1;
                  }
              
                  private void swap(int[] array, int i, int j) {
                      int temp = array[i];
                      array[i] = array[j];
                      array[j] = temp;
                  }
              }
              
              class MergeSort implements Sortable {
                  
                  public void sort(int[] array) {
                      mergeSort(array, 0, array.length - 1);
                  }
              
                  private void mergeSort(int[] array, int low, int high) {
                      if (low < high) {
                          int mid = (low + high) / 2;
                          mergeSort(array, low, mid);
                          mergeSort(array, mid + 1, high);
                          merge(array, low, mid, high);
                      }
                  }
              
                  private void merge(int[] array, int low, int mid, int high) {
                      int[] temp = new int[array.length];
                      for (int i = low; i <= high; i++) {
                          temp[i] = array[i];
                      }
              
                      int i = low;
                      int j = mid + 1;
                      int k = low;
              
                      while (i <= mid && j <= high) {
                          if (temp[i] >= temp[j]) {
                              array[k] = temp[i];
                              i++;
                          } else {
                              array[k] = temp[j];
                              j++;
                          }
                          k++;
                      }
              
                      while (i <= mid) {
                          array[k] = temp[i];
                          i++;
                          k++;
                      }
                  }
              }
              
              public class interfaces11_7024 {
                  public static void main(String[] args) {
                      int[] array = {2, 8, 70, 1, 53};
              
                      Sortable quickSort = new QuickSort();
                      quickSort.sort(array);
                      System.out.print("QuickSort: ");
                      printArray(array);
              
                      Sortable mergeSort = new MergeSort();
                      mergeSort.sort(array);
                      System.out.print("MergeSort: ");
                      printArray(array);
                  }
              
                  private static void printArray(int[] array) {
                      for (int num : array) {
                          System.out.print(num + " ");
                      }
                      System.out.println();
                  }
              }