Waste less time on Facebook — follow Brilliant.
×

Sorting Algorithms

Highly-organized data can be critical for many algorithms, and often you want your data ordered from least to greatest. The art of getting your data in order is trickier than you might think!

Merge/Quicksort

     

When two sorted arrays \(A\) and \(B\) are merged into one big sorted array \(C\). What is \(C[400] (mod) \ 12 \)(the remainder of the element with index 400 in \(C\) when divided by 12)?

\(A = \{ F_i \| 0 \leq i \leq 10000 \} \) \(B = \{ i! \| 0 \leq i \leq 1000 \} \)

Details and assumptions

  • \(F_i\) is the \(i\)th Fibonacci number. \(F_0 = 0 \ , F_1 = 1 , F_2 = 1 , ... \)

  • \(n!\) is the factorial of \(n\) .\( 3! = 3\times2\times1\).

View solution
View wiki
by Brilliant Staff

The MergeSort(array) method itself is surprisingly simple. The meat of the algorithm is within the auxiliary method Merge. The implementation of mergesort is correct(assuming the Merge method is also correct). It should properly sort any given array of integers. The conditional(Line 5) which handles the base case of the recursion however is noticeably missing. Which of the following code segments correctly fills the empty line?

1
2
3
4
5
6
7
8
def MergeSort( array ):
   middle = len(array)/2 #Middle = size(array)/2
   A = array[0:middle]# A = array[0..middle
   B = array[middle::]# B=array[middle..end]
   #if ... MISSING !!!!!
      return Merge(A,B)
   else:
      return Merge(MergeSort(A),MergeSort(B))
View solution
View wiki
by Brilliant Staff

Merge-sort is a sorting algorithm that works by splitting a given array \(A\) into two sub arrays \(\{A_p,\ldots,A_q\}\) and \(\{A_{q+1},\ldots,A_r\}\), which are then sorted individually. Once the two arrays are sorted, they are combined to give the overall sorted array.

Merge-sort usually involves two methods: one for merging two sorted arrays and one for the sorting itself.

If \(A\) is the array containing the first half of the sorted items in \(\{A_0,\ldots,A_p\}\) and the second half in \(\{A_{p+1},\ldots,A_r\}\), merge(A,p,r) can be implemented as follows:

1
2
3
4
5
merge_sort(A):
      q = len(A) / 2
      A_left  = merge_sort(A[0:q]
      A_right = merge_sort(A[q:-1])
      return merge(A_left, A_right)

In classic merge-sort we are able to carry out the merging/dividing operation in linear time. For this problem however, assume we are unable to achieve such efficiency and instead the process of merging takes quadratic time(\(O(n^2)\)).

What is the running time of this version of merge-sort?

View solution
View wiki
by Brilliant Staff
×

Problem Loading...

Note Loading...

Set Loading...