Impact verses vacuum How do asteroids, comets and other stuff stay together when colliding in the empty vacuum of space, when they are made up of non-sticky substances like rock?

My understanding is that the force of gravity from small objects is very weak and when travelling at speed I don’t see how they join together.
All these objects are rocky, also the icy ones given the low temparatures at their usual orbits. Your observation is also correct, that mutual collisions at usual orbital velocities in today's solar system tend to be catastrophic among the remaining small objects (comets, asteroids, KBOs etc); that is even true when you consider that usual collision velocities are smaller than orbital velocities as most objects rotate prograde and only objects in similar orbits collide with approx. differential Keplerian velocities. The objects don't grow anymore today.

The collisions you likely refer to occur during planet formation. Planet formation happens concurrent to star formation inside the star's accretion disk which evolves into a protoplanetary disk around the pre-main sequence star. This protoplanetary disk consists of both, gas and solid particles (mass ratio ~100:1) so that motion of the objects is not in vacuum but influenced by the gas - the smaller the more. The outcome (sticking, bouncing, fragmentation) of mutual collisions depends on what the particles look like (how porous or compact) and what is their relative size which defines for small particles their collision speed. You can extend these physics to larger particles until they reach a size at which their motion decouples from the gas. Then likely processes kick-in which combine the motion of gas and interaction with collective behaviour of these 'pebbles' (like disk turbulence, streaming instability which forms zones or vortices in the protoplanetary disk in which the small bodies can amass and gently collide to form big bodies, etc), so that these pebbles agglomerate to larger bodies, the so-called planetesimals which are of a few km-size like today's comets. 

These bodies are big enough that they are only little affected by gas - the bigger the less drag compared to their mass they experience and thus will rotate with Keplarian speed around the being-born star - and catching up with smaller bodies in the same or very similar orbit, so that they gather them to form even bigger bodies. Thus a few 'lucky winners' will experience run-away growth, collecting the smaller bodies in their orbital distance which increases even more the bigger they become as gravity will start to play a role. The star enters main sequence and the emerging solar wind will push out the gas of the disk so that a debris disk, thus big particles, planetesimals and protoplanets remain, entering the phase of late heavy bombardment where many small bodies collide with the bigger bodies, effectively clearing especially the inner part of the solar system from many small bodies (as the collision timescale is particularily short)

Many, many details have been left-out here, of course and in parts it may even be over-simplified.

So in essence: what you see in the videos only works because there is still gas which slows down things - and because stuff is in similar orbits and thus their relative velocity is small so that gravity is NOT overcome by the shattered bodies when they collide.