In terms of references and their implementation on the heap and the stack, how is
equality testing for arrays different from that for integers? 

This is to do with Java programming, if you have a stack and a heap, would equality testing for example j == i be the same for arrays and for integers? I understand that arrays, are stored in the heap and the stack, as it holds bulks of data, but integers are only stored in the stack and referenced in the heap.



I understand for equality testing j==i (variables) the stack pointer will point to the same location.

I'm confused on how j==i would be different for array and integers.

Could someone explain? 

This is a special case of a selection algorithm that can find the $k$th smallest element of an array with $k$ is the half of the size of the array. There is an implementation that is linear in the worst case.

Generic selection algorithm

First let's see an algorithm find-kth that finds the $k$th smallest element of an array:

find-kth(A, k)
  pivot = random element of A
  (L, R) = split(A, pivot)
  if k = |L|+1, return pivot
  if k ≤ |L|  , return find-kth(L, k)
  if k > |L|+1, return find-kth(R, k-(|L|+1))


The function split(A, pivot) returns L,R such that all elements in R are greater than pivot and L all the others (minus one occurrence of pivot). Then all is done recursively.

This is $O(n)$ in average but $O(n^2)$ in the worst case.

Linear worst case: the median-of-medians algorithm

A better pivot is the median of all the medians of sub arrays of A of size 5, by using calling the procedure on the array of these medians.

find-kth(A, k)
  B = [median(A[1], .., A[5]), median(A[6], .., A[10]), ..]
  pivot = find-kth(B, |B|/2)
  ...


This guarantees $O(n)$ in all cases. It is not that obvious. These powerpoint slides are helpful both at explaining the algorithm and the complexity.

Note that most of the time using a random pivot is faster.
