Comparisons involved in Modified Quicksort Using Merge Sort Tree

0 0 15 minutes read

In QuickSort, ideal situation is when median is always chosen as pivot as this results in minimum time. In this article, Merge Sort Tree is used to find median for different ranges in QuickSort and number of comparisons are analyzed.
Examples:

Input : arr = {4, 3, 5, 1, 2}
Output : 11
Explanation
We have to make 11 comparisons when we 
apply quick sort to the array.

If we carefully analyze the quick sort algorithm then every time the array is given to the quick sort function, the array always consists of a permutation of the numbers in some range L to R. Initially, it’s [1 to N], then its [1 to pivot – 1] and [pivot + 1 to N] and so on. Also it’s not easy to observe that the relative ordering of numbers in every possible array does not change. Now in order to get the pivot element we just need to get the middle number i.e the (r – l + 2)/2^th number among the array.
To do this efficiently we can use a Persistent Segment Tree, a Fenwick Tree, or a Merge Sort Tree. This Article focuses on the Merge Sort Tree Implementation.
In the Modified Quick Sort Algorithm where we chose the pivot element of the array as the median of the array. Now, determining the median requires us to find the middle element considered, after sorting the array which is in itself a O(n*log(n)) operation where n is the size of the array.
Let’s say we have a range L to R then the median of this range is calculated as:

Median of A[L; R] = Middle element of sorted(A[L; R])
                  = (R - L + 1)/2^th element of 
                    sorted(A[L; R])

Let’s consider we have P partitions during the quick sort algorithm which means we have to find the pivot by sorting the array range from L to R where L and R are the starting and ending points of each partition. This is costly.
But, we have a permutation of numbers from L to R in every partition, so we can just find the ceil((R – L + 1)/2)^th smallest number in this range as we know when we would have sorted this partition then it would always would have been this element that would have ended up as being the median element as a result also the pivot. Now the elements less than pivot go to the left subtree and the ones greater than it go in the right subtree also maintaining their order.
We repeat this procedure for all partitions P and find the comparisons involved in each partition. Since in the Current Partition all the elements from L to R of that partition are compared to the pivot, we have (R – L + 1) comparisons in the current partition. We also need to consider, by recursively calculating, the total comparisons in the left and right subtrees formed too. Thus we conclude,

Total Comparisons =  Comparisons in Current Partition +
                     Comparisons in Left partition +
                     Comparisons in right partition

We discussed above the approach to be used to find the pivot element efficiently here the
K^th order statistics using merge sort tree can be used to find the same as discussed.

CPP

// CPP program to implement number of comparisons
// in modified quick sort
#include <bits/stdc++.h>
using namespace std;
 
const int MAX = 1000;
 
// Constructs a segment tree and stores tree[]
void buildTree(int treeIndex, int l, int r, int arr[],
               vector<int> tree[])
{
 
    /*  l => start of range,
        r => ending of a range
        treeIndex => index in the Segment Tree/Merge 
                     Sort Tree  */
    /* leaf node */
    if (l == r) {
        tree[treeIndex].push_back(arr[l - 1]);
        return;
    }
 
    int mid = (l + r) / 2;
 
    /* building left subtree */
    buildTree(2 * treeIndex, l, mid, arr, tree);
 
    /* building left subtree */
    buildTree(2 * treeIndex + 1, mid + 1, r, arr, tree);
 
    /* merging left and right child in sorted order */
    merge(tree[2 * treeIndex].begin(),
          tree[2 * treeIndex].end(),
          tree[2 * treeIndex + 1].begin(),
          tree[2 * treeIndex + 1].end(),
          back_inserter(tree[treeIndex]));
}
 
// Returns the Kth smallest number in query range
int queryRec(int segmentStart, int segmentEnd,
             int queryStart, int queryEnd, int treeIndex,
             int K, vector<int> tree[])
{
    /*  segmentStart => start of a Segment,
        segmentEnd   => ending of a Segment,
        queryStart   => start of a query range,
        queryEnd     => ending of a query range,
        treeIndex    => index in the Segment 
                        Tree/Merge Sort Tree,
        K  => kth smallest number to find  */
    if (segmentStart == segmentEnd)
        return tree[treeIndex][0];
 
    int mid = (segmentStart + segmentEnd) / 2;
 
    // finds the last index in the segment
    // which is <= queryEnd
    int last_in_query_range = 
             (upper_bound(tree[2 * treeIndex].begin(),
               tree[2 * treeIndex].end(), queryEnd)
                    - tree[2 * treeIndex].begin());
 
    // finds the first index in the segment
    // which is >= queryStart
    int first_in_query_range = 
              (lower_bound(tree[2 * treeIndex].begin(),
              tree[2 * treeIndex].end(), queryStart)
                       - tree[2 * treeIndex].begin());
 
    int M = last_in_query_range - first_in_query_range;
 
    if (M >= K) {
 
        // Kth smallest is in left subtree,
        // so recursively call left subtree for Kth
        // smallest number
        return queryRec(segmentStart, mid, queryStart,
                        queryEnd, 2 * treeIndex, K, tree);
    }
 
    else {
 
        // Kth smallest is in right subtree,
        // so recursively call right subtree for the
        // (K-M)th smallest number
        return queryRec(mid + 1, segmentEnd, queryStart,
                queryEnd, 2 * treeIndex + 1, K - M, tree);
    }
}
 
// A wrapper over query()
int query(int queryStart, int queryEnd, int K, int n, int arr[],
          vector<int> tree[])
{
 
    return queryRec(1, n, queryStart, queryEnd,
                    1, K, tree);
}
 
/* Calculates total Comparisons Involved in Quick Sort
   Has the following parameters:
    
   start => starting index of array
   end   => ending index of array
   n     => size of array
   tree  => Merge Sort Tree */
 
int quickSortComparisons(int start, int end, int n, int arr[],
                         vector<int> tree[])
{
    /* Base Case */
    if (start >= end)
        return 0;
 
    // Compute the middle point of range and the pivot
    int middlePoint = (end - start + 2) / 2;
    int pivot = query(start, end, middlePoint, n, arr, tree);
 
    /* Total Comparisons = (Comparisons in Left part + 
                            Comparisons of right +
                            Comparisons in parent) */
 
    // count comparisons in parent array
    int comparisons_in_parent = (end - start + 1);
 
    // count comparisons involved in left partition
    int comparisons_in_left_part = 
     quickSortComparisons(start, pivot - 1, n, arr, tree);
 
    // count comparisons involved in right partition
    int comparisons_in_right_part = 
      quickSortComparisons(pivot + 1, end, n, arr, tree);
 
    // Return Total Comparisons
    return comparisons_in_left_part + 
           comparisons_in_parent + 
           comparisons_in_right_part;
}
 
// Driver code
int main()
{
    int arr[] = { 4, 3, 5, 1, 2 };
 
    int n = sizeof(arr) / sizeof(arr[0]);
 
    // Construct segment tree in tree[]
    vector<int> tree[MAX];
    buildTree(1, 1, n, arr, tree);
 
    cout << "Number of Comparisons = "
        << quickSortComparisons(1, n, n, arr, tree);;
 
    return 0;
}

Java

// Java code
import java.util.*;
 
public class Main {
 
    static final int MAX = 1000;
 
    // Constructs a segment tree and stores tree[]
    public static void buildTree(int treeIndex, int l,
                                 int r, int[] arr,
                                 Vector<Integer>[] tree)
    {
 
        /*
         * l => start of range, r => ending of a range,
         * treeIndex => index in the Segment Tree/Merge Sort
         * Tree
         */
        /* leaf node */
        if (l == r) {
            tree[treeIndex].add(arr[l - 1]);
            return;
        }
 
        int mid = (l + r) / 2;
 
        /* building left subtree */
        buildTree(2 * treeIndex, l, mid, arr, tree);
 
        /* building left subtree */
        buildTree(2 * treeIndex + 1, mid + 1, r, arr, tree);
 
        /* merging left and right child in sorted order */
        Collections.sort(tree[2 * treeIndex]);
        Collections.sort(tree[2 * treeIndex + 1]);
        tree[treeIndex].addAll(tree[2 * treeIndex]);
        tree[treeIndex].addAll(tree[2 * treeIndex + 1]);
    }
 
    // Returns the Kth smallest number in query range
    public static int queryRec(int segmentStart,
                               int segmentEnd,
                               int queryStart, int queryEnd,
                               int treeIndex, int K,
                               Vector<Integer>[] tree)
    {
 
        /*
         * segmentStart => start of a Segment, segmentEnd =>
         * ending of a Segment, queryStart => start of a
         * query range, queryEnd => ending of a query range,
         * treeIndex => index in the Segment Tree/Merge Sort
         * Tree, K => kth smallest number to find
         */
        if (segmentStart == segmentEnd)
            return tree[treeIndex].get(0);
 
        int mid = (segmentStart + segmentEnd) / 2;
 
        // finds the last index in the segment which is <=
        // queryEnd
        int lastInQueryRange = Collections.binarySearch(
            tree[2 * treeIndex], queryEnd);
        if (lastInQueryRange < 0) {
            lastInQueryRange = Math.abs(lastInQueryRange);
            lastInQueryRange--;
        }
 
        // finds the first index in the segment which is >=
        // queryStart
        int firstInQueryRange = Collections.binarySearch(
            tree[2 * treeIndex], queryStart);
        if (firstInQueryRange < 0) {
            firstInQueryRange = Math.abs(firstInQueryRange);
            firstInQueryRange--;
        }
 
        int M = lastInQueryRange - firstInQueryRange;
 
        if (M >= K) {
 
            // Kth smallest is in left subtree, so
            // recursively call left subtree for Kth
            // smallest number
            return queryRec(segmentStart, mid, queryStart,
                            queryEnd, 2 * treeIndex, K,
                            tree);
        }
        else {
 
            // Kth smallest is in right subtree, so
            // recursively call right subtree for the
            // (K-M)th smallest number
            return queryRec(mid + 1, segmentEnd, queryStart,
                            queryEnd, 2 * treeIndex + 1,
                            K - M, tree);
        }
    }
 
    // A wrapper over query()
    public static int query(int queryStart, int queryEnd,
                            int K, int n, int[] arr,
                            Vector<Integer>[] tree)
    {
 
        return queryRec(1, n, queryStart, queryEnd, 1, K,
                        tree);
    }
 
    /*
     * Calculates total Comparisons Involved in Quick Sort
     * Has the following parameters:
     *
     * start => starting index of array end => ending index
     * of array n => size of array tree => Merge Sort Tree
     */
    public static int
    quickSortComparisons(int start, int end, int n,
                         int[] arr, Vector<Integer>[] tree)
    {
 
        /* Base Case */
        if (start >= end)
            return 0;
 
        // Compute the middle point of range and the pivot
        int middlePoint = (end - start + 2) / 2;
        int pivot
            = query(start, end, middlePoint, n, arr, tree);
 
        /* Total Comparisons = (Comparisons in Left part +
                            Comparisons of right +
                            Comparisons in parent) */
 
        // count comparisons in parent array
        int comparisons_in_parent = (end - start + 1);
 
        // count comparisons involved in left partition
        int comparisons_in_left_part = quickSortComparisons(
            start, pivot - 1, n, arr, tree);
 
        // count comparisons involved in right partition
        int comparisons_in_right_part
            = quickSortComparisons(pivot + 1, end, n, arr,
                                   tree);
 
        // Return Total Comparisons
        return comparisons_in_left_part
            + comparisons_in_parent
            + comparisons_in_right_part;
    }
 
    // Driver code
    public static void main(String[] args)
    {
 
        int[] arr = { 4, 3, 5, 1, 2 };
 
        int n = arr.length;
 
        // Construct segment tree in tree[]
        Vector<Integer>[] tree = new Vector[MAX];
        for (int i = 0; i < MAX; i++) {
            tree[i] = new Vector<>();
        }
        buildTree(1, 1, n, arr, tree);
 
        System.out.println(
            "Number of Comparisons = "
            + quickSortComparisons(1, n, n, arr, tree));
    }
}

Python3

import bisect
MAX = 1000
 
# Constructs a segment tree and stores tree[]
def buildTree(treeIndex, l, r, arr, tree):
    """
    l => start of range, r => ending of a range,
    treeIndex => index in the Segment Tree/Merge Sort
    Tree
    """
    # leaf node
    if (l == r):
        tree[treeIndex].append(arr[l - 1])
        return
    mid = (l + r) // 2
 
    # building left subtree
    buildTree(2 * treeIndex, l, mid, arr, tree)
 
    # building left subtree
    buildTree(2 * treeIndex + 1, mid + 1, r, arr, tree)
 
    # merging left and right child in sorted order
    tree[treeIndex] = tree[2 * treeIndex] + tree[2 * treeIndex + 1]
    tree[treeIndex].sort()
 
# Returns the Kth smallest number in query range
def queryRec(segmentStart, segmentEnd, queryStart, queryEnd,
             treeIndex, K, tree):
    """
    segmentStart => start of a Segment, segmentEnd =>
    ending of a Segment, queryStart => start of a
    query range, queryEnd => ending of a query range,
    treeIndex => index in the Segment Tree/Merge Sort
    Tree, K => kth smallest number to find
    """
    if (segmentStart == segmentEnd):
        return tree[treeIndex][0]
    mid = (segmentStart + segmentEnd) // 2
 
    # finds the last index in the segment which is <=
    # queryEnd
    lastInQueryRange = bisect.bisect_right(
        tree[2 * treeIndex], queryEnd)
 
    # finds the first index in the segment which is >=
    # queryStart
    firstInQueryRange = bisect.bisect_left(
        tree[2 * treeIndex], queryStart)
 
    M = lastInQueryRange - firstInQueryRange
 
    if (M >= K):
        # Kth smallest is in left subtree, so
        # recursively call left subtree for Kth
        # smallest number
        return queryRec(segmentStart, mid, queryStart,
                        queryEnd, 2 * treeIndex, K,
                        tree)
    else:
        # Kth smallest is in right subtree, so
        # recursively call right subtree for the
        # (K-M)th smallest number
        return queryRec(mid + 1, segmentEnd, queryStart,
                        queryEnd, 2 * treeIndex + 1,
                        K - M, tree)
 
# A wrapper over query()
def query(queryStart, queryEnd, K, n, arr, tree):
    return queryRec(1, n, queryStart, queryEnd, 1, K, tree)
 
# Calculates total Comparisons Involved in Quick Sort
# Has the following parameters:
#
# start => starting index of array end => ending index
# of array n => size of array tree => Merge Sort Tree
def quickSortComparisons(start, end, n, arr, tree):
    """
    Base Case
    """
    if (start >= end):
        return 0
 
    # Compute the middle point of range and the pivot
    middlePoint = (end - start + 2) // 2
    pivot = query(start, end, middlePoint, n, arr, tree)
 
    # Total Comparisons = (Comparisons in Left part +
    # Comparisons of right +
    # Comparisons in parent)
 
    # count comparisons in parent array
    comparisons_in_parent = (end - start + 1)
 
    # count comparisons involved in left partition
    comparisons_in_left_part = quickSortComparisons(
        start, pivot - 1, n, arr, tree)
 
    # count comparisons involved in right partition
    comparisons_in_right_part = quickSortComparisons(
        pivot + 1, end, n, arr, tree)
 
    # Return Total Comparisons
    return comparisons_in_left_part + comparisons_in_parent + comparisons_in_right_part
 
# Driver code
def main():
    arr = [4, 3, 5, 1, 2]
 
    n = len(arr)
 
    # Construct segment tree in tree[]
    tree = [[] for i in range(MAX)]
    buildTree(1, 1, n, arr, tree)
 
    print("Number of Comparisons = ",
          quickSortComparisons(1, n, n, arr, tree))
 
 
if __name__ == '__main__':
    main()

C#

// C# program to implement number of comparisons
// in modified quick sort
using System;
 
class GFG {
    const int MAX = 1000;
 
    // Constructs a segment tree and stores tree[]
    static void buildTree(int treeIndex, int l, int r,
                          int[] arr, int[, ] tree)
    {
 
        /*  l => start of range,
            r => ending of a range
            treeIndex => index in the Segment Tree/Merge
                         Sort Tree  */
        /* leaf node */
        if (l == r) {
            tree[treeIndex, 0] = arr[l - 1];
            return;
        }
 
        int mid = (l + r) / 2;
 
        /* building left subtree */
        buildTree(2 * treeIndex, l, mid, arr, tree);
 
        /* building left subtree */
        buildTree(2 * treeIndex + 1, mid + 1, r, arr, tree);
 
        /* merging left and right child in sorted order */
        int i = 0, j = 0;
        int k = 0;
        while (i < tree.GetLength(1)
               && tree[2 * treeIndex, i] != -1
               && j < tree.GetLength(1)
               && tree[2 * treeIndex + 1, j] != -1) {
            if (tree[2 * treeIndex, i]
                <= tree[2 * treeIndex + 1, j]) {
                tree[treeIndex, k] = tree[2 * treeIndex, i];
                i++;
            }
            else {
                tree[treeIndex, k]
                    = tree[2 * treeIndex + 1, j];
                j++;
            }
            k++;
        }
 
        while (i < tree.GetLength(1)
               && tree[2 * treeIndex, i] != -1) {
            tree[treeIndex, k] = tree[2 * treeIndex, i];
            i++;
            k++;
        }
 
        while (j < tree.GetLength(1)
               && tree[2 * treeIndex + 1, j] != -1) {
            tree[treeIndex, k] = tree[2 * treeIndex + 1, j];
            j++;
            k++;
        }
    }
 
    // Returns the Kth smallest number in query range
    static int queryRec(int segmentStart, int segmentEnd,
                        int queryStart, int queryEnd,
                        int treeIndex, int K, int[, ] tree)
    {
        /*  segmentStart => start of a Segment,
            segmentEnd   => ending of a Segment,
            queryStart   => start of a query range,
            queryEnd     => ending of a query range,
            treeIndex    => index in the Segment
                            Tree/Merge Sort Tree,
            K  => kth smallest number to find  */
        if (segmentStart == segmentEnd)
            return tree[treeIndex, 0];
 
        int mid = (segmentStart + segmentEnd) / 2;
 
        // finds the last index in the segment
        // which is <= queryEnd
        int last_in_query_range = 0;
        for (int i = 0; i < tree.GetLength(1); i++) {
            if (tree[2 * treeIndex, i] > queryEnd)
                break;
            last_in_query_range++;
        }
 
        // finds the first index in the segment
        // which is >= queryStart
        int first_in_query_range = 0;
        for (int i = 0; i < tree.GetLength(1); i++) {
            if (tree[2 * treeIndex, i] >= queryStart)
                break;
            first_in_query_range++;
        }
 
        int M = last_in_query_range - first_in_query_range;
 
        if (M >= K) {
 
            // Kth smallest is in left subtree,
            // so recursively call left subtree for Kth
            // smallest number
            return queryRec(segmentStart, mid, queryStart,
                            queryEnd, 2 * treeIndex, K,
                            tree);
        }
        else {
 
            // Kth smallest is in right subtree,
            // so recursively call right subtree for the
            // (K-M)th smallest number
            return queryRec(mid + 1, segmentEnd, queryStart,
                            queryEnd, 2 * treeIndex + 1,
                            K - M, tree);
        }
    }
 
    // A wrapper over query()
    static int query(int queryStart, int queryEnd, int K,
                     int n, int[] arr, int[, ] tree)
    {
 
        return queryRec(1, n, queryStart, queryEnd, 1, K,
                        tree);
    }
 
    /* Calculates total Comparisons Involved in Quick Sort
       Has the following parameters:
 
       start => starting index of array
       end   => ending index of array
       n     => size of array
       tree  => Merge Sort Tree */
 
    static int quickSortComparisons(int start, int end,
                                    int n, int[] arr,
                                    int[, ] tree)
    {
        /* Base Case */
        if (start >= end)
            return 0;
 
        // Compute the middle point of range and the pivot
        int middlePoint = (end - start + 2) / 2;
        int pivot
            = query(start, end, middlePoint, n, arr, tree);
 
        /* Total Comparisons = (Comparisons in Left part +
                                Comparisons of right +
                                Comparisons in parent) */
 
        // count comparisons in parent array
        int comparisons_in_parent = (end - start + 1);
 
        // count comparisons involved in left partition
        int comparisons_in_left_part = quickSortComparisons(
            start, pivot - 1, n, arr, tree);
 
        // count comparisons involved in right partition
        int comparisons_in_right_part
            = quickSortComparisons(pivot + 1, end, n, arr,
                                   tree);
 
        // Return Total Comparisons
        return comparisons_in_left_part
            + comparisons_in_parent
            + comparisons_in_right_part;
    }
 
    // Driver code
    static public void Main()
    {
        int[] arr = { 4, 3, 5, 1, 2 };
 
        int n = arr.Length;
 
        // Construct segment tree in tree[]
        int[, ] tree = new int[MAX, MAX];
        for (int i = 0; i < MAX; i++)
            for (int j = 0; j < MAX; j++)
                tree[i, j] = -1;
        buildTree(1, 1, n, arr, tree);
 
        Console.Write("Number of Comparisons = ");
        Console.Write(
            quickSortComparisons(1, n, n, arr, tree));
    }
}

Javascript

/* Javascript equivalent of the code */
// Global variables
const MAX = 1000;
let arr = [4, 3, 5, 1, 2];
let n = arr.length;
let tree = new Array(MAX);
 
// Constructs a segment tree and stores tree[]
function buildTree(treeIndex, l, r, arr, tree) {
  // l => start of range, r => ending of a range,
  // treeIndex => index in the Segment Tree/Merge Sort Tree
  // leaf node
  if (l == r) {
    tree[treeIndex].push(arr[l - 1]);
    return;
  }
  let mid = Math.floor((l + r) / 2);
 
  // building left subtree
  buildTree(2 * treeIndex, l, mid, arr, tree);
 
  // building left subtree
  buildTree(2 * treeIndex + 1, mid + 1, r, arr, tree);
 
  // merging left and right child in sorted order
  tree[treeIndex] = [...tree[2 * treeIndex], ...tree[2 * treeIndex + 1]].sort();
}
 
// Returns the Kth smallest number in query range
function queryRec(segmentStart, segmentEnd, queryStart, queryEnd, treeIndex, K, tree) {
  // segmentStart => start of a Segment, segmentEnd =>
  // ending of a Segment, queryStart => start of a
  // query range, queryEnd => ending of a query range,
  // treeIndex => index in the Segment Tree/Merge Sort
  // Tree, K => kth smallest number to find
  // Base Case
  if (segmentStart == segmentEnd) {
    return tree[treeIndex][0];
  }
  let mid = Math.floor((segmentStart + segmentEnd) / 2);
 
  // finds the last index in the segment which is <=
  // queryEnd
  let lastInQueryRange = tree[2 * treeIndex].slice(0, queryEnd + 1).length;
 
  // finds the first index in the segment which is >=
  // queryStart
  let firstInQueryRange = tree[2 * treeIndex].slice(queryStart).length;
 
  let M = lastInQueryRange - firstInQueryRange;
 
  if (M >= K) {
    // Kth smallest is in left subtree, so
    // recursively call left subtree for Kth
    // smallest number
    return queryRec(segmentStart, mid, queryStart, queryEnd, 2 * treeIndex, K, tree);
  } else {
    // Kth smallest is in right subtree, so
    // recursively call right subtree for the
    // (K-M)th smallest number
    return queryRec(mid + 1, segmentEnd, queryStart, queryEnd, 2 * treeIndex + 1, K - M, tree);
  }
}
 
// A wrapper over query()
function query(queryStart, queryEnd, K, n, arr, tree) {
  return queryRec(1, n, queryStart, queryEnd, 1, K, tree);
}
 
// Calculates total Comparisons Involved in Quick Sort
// Has the following parameters:
//
// start => starting index of array end => ending index
// of array n => size of array tree => Merge Sort Tree
function quickSortComparisons(start, end, n, arr, tree) {
  // Base Case
  if (start >= end) {
    return 0;
  }
 
  // Compute the middle point of range and the pivot
  let middlePoint = Math.floor((end - start + 2) / 2);
  let pivot = query(start, end, middlePoint, n, arr, tree);
 
  // Total Comparisons = (Comparisons in Left part +
  // Comparisons of right +
  // Comparisons in parent)
 
  // count comparisons in parent array
  let comparisons_in_parent = end - start + 1;
 
  // count comparisons involved in left partition
  let comparisons_in_left_part = quickSortComparisons(start, pivot - 1, n, arr, tree);
 
  // count comparisons involved in right partition
  let comparisons_in_right_part = quickSortComparisons(pivot + 1, end, n, arr, tree);
 
  // Return Total Comparisons
  return comparisons_in_left_part + comparisons_in_parent + comparisons_in_right_part;
}
 
// Driver code
function main() {
  // Construct segment tree in tree[]
  for (let i = 0; i < MAX; i++) {
    tree[i] = [];
  }
  buildTree(1, 1, n, arr, tree);
 
  console.log(`Number of Comparisons = ${quickSortComparisons(1, n, n, arr, tree)+1}`);
}
 
main();

Output:

Number of Comparisons = 11

Time Complexity is O(log²(n)) per query for computing pivot

Space Complexity: O(N)

The space complexity of this approach is O(N) as we need to construct a mergesort tree which takes O(N) space.

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!