tar doesn't sort entries on archive creation time. I've tried to use it to compare trees in the past, to notice this caveat. It's a detail most people don't seem to realize about their file system, but files aren't (usually, on most FSes) sorted in any particular order. By creation time order, MAYBE (no guarantee, often not), but as directories get modified and files are deleted an added, this gets clobbered anyhow. Use "ls -f" to see the raw, unsorted list of a directory's contents. Since it is faster for tar to just use this, than to pre-sort entries, that's the order they'll get added in.

What you want is a tar that is deterministically identical regardless of the underlying file system's order. Sadly, no such option exists in GNU tar, but that doesn't quite mean the end of the quest. Behold:

find bin -print0 | sort -Vz | tar -cf bin.tar --no-recursion --null -T -

The first two shouldn't be hard to parse. Find files, separated by NULL characters (so any whitespace or other special characters won't be an issue), pass that onto "sort" that uses a version sort (identical rules to dpkg version sorting, and will disregard the locale sort) and interpret entries as being between NULLs (as well as emit them, likewise). The tar command should be pretty self-explanatory, but the "-T -" tells it to read stdin for a file list, with --null specifying that the input list is separated by NULLs, and --no-recursion prevents it from recursing into directories, instead just adding an entry in the tar for directories -- the find|sort will take care of the directory members already, sorted. Optionally add --numeric-owner to tar, if you want to compare trees on different computers, but results might vary (rsync and tar normally send/store both the id and name, and if the "name" exists on the local machine, uses that instead of id).