private static int[] merge(int[] set,int[] tmp){
  List<Integer> newSet=new ArrayList<Integer>();
  int setLength=(set == null ? 0 : set.length);
  int seti=0;
  int tmpi=0;
  while (seti < setLength || tmpi < tmp.length) {
    if (seti >= setLength) {
      int tmpVal=tmp[tmpi];
      newSet.add(tmpVal);
      tmpi++;
      tmpi=consumeDuplicates(tmp,getSparseIndex(tmpVal),tmpi);
    }
 else     if (tmpi >= tmp.length) {
      newSet.add(set[seti++]);
    }
 else {
      int setVal=set[seti];
      int tmpVal=tmp[tmpi];
      if (getSparseIndex(setVal) == getSparseIndex(tmpVal)) {
        newSet.add(Math.min(setVal,tmpVal));
        tmpi++;
        tmpi=consumeDuplicates(tmp,getSparseIndex(tmpVal),tmpi);
        seti++;
      }
 else       if (getSparseIndex(setVal) < getSparseIndex(tmpVal)) {
        newSet.add(setVal);
        seti++;
      }
 else {
        newSet.add(tmpVal);
        tmpi++;
        tmpi=consumeDuplicates(tmp,getSparseIndex(tmpVal),tmpi);
      }
    }
  }
  return toIntArray(newSet);
}

private static int [ ] merge ( int [ ] set , int [ ] tmp ) { List < Integer > newSet = new ArrayList < Integer > ( ) ; int setLength = ( set == null ? 0 : set . length ) ; int seti = 0 ; int tmpi = 0 ; while ( seti < setLength || tmpi < tmp . length ) { if ( seti >= setLength ) { int tmpVal = tmp [ tmpi ] ; newSet . add ( tmpVal ) ; tmpi ++ ; tmpi = consumeDuplicates ( tmp , getSparseIndex ( tmpVal ) , tmpi ) ; } else if ( tmpi >= tmp . length ) { newSet . add ( set [ seti ++ ] ) ; } else { int setVal = set [ seti ] ; int tmpVal = tmp [ tmpi ] ; if ( getSparseIndex ( setVal ) == getSparseIndex ( tmpVal ) ) { newSet . add ( Math . min ( setVal , tmpVal ) ) ; tmpi ++ ; tmpi = consumeDuplicates ( tmp , getSparseIndex ( tmpVal ) , tmpi ) ; seti ++ ; } else if ( getSparseIndex ( setVal ) < getSparseIndex ( tmpVal ) ) { newSet . add ( setVal ) ; seti ++ ; } else { newSet . add ( tmpVal ) ; tmpi ++ ; tmpi = consumeDuplicates ( tmp , getSparseIndex ( tmpVal ) , tmpi ) ; } } } return toIntArray ( newSet ) ; }
batch merges the sparse set with the temporary list . usually called when the temporary list fills up , but may also be needed when suddenly converting to normal or producing a cardinality estimate . < p / > it works very similarly to the merge part of merge sort with some key differences : we don ' t care about the kind of order the idxs appear in , only that they are in some order . this is because we only need to be sure that we detect when they are the same . so if idx : ' 001 ' appears first and idx : ' 002 ' appears last , that is fine as long as that behavior is the same for both lists . < p / > we do not allow duplicate entries ( we are making a set after all ) , and collisions are resolved by run length . however , most of the time the run length will be the same if two idx ' are the same . only in the 1 in ~ 128 chance case of ' all 0s ? ' will they differ . because the rest of the encoding is the same we can do comparisons without extracting the run length and because of our earlier inversion trick , the highest run length duplicates will appear first . so we take those and ignore any that follow with the same idx ' .
