It just seems like you have two 3-wire cables (with constant and switched hots) going into and out of that box, along with a 2-wire constant feed. It's not two circuits. The reds are switched and the blacks are constant hot.
IMO I would pigtail each color and use the side screws on the receptacle just like they were before.
That looks like #12 so you can no longer use the backstab/quickwire holes in the back of receptacles (in the US at least).
First, your illustrations are Mad Awesome. You could illustrate electrical books. Literally. You might even talk to Mike Holt or others doing electrical docs.
You still have some knowledge gaps, so I'd school up some more. For a guy as smart as you, knowledge is cheap.
If you are good at visual, stay with that. Buy a variety-pack of electrical tape colors, and a couple feet of 12/3 cable because it's a cheap way to get a variety of wire colors for pigtails. 12 gauge is the universal donor size, it is acceptable on any common 120v circuit up to 20 amp breaker. 14ga is only allowed on 15A breakers/with 14ga wire.
First, permanently wrap (tag) the white wire of cable C with red tape. From your comments elsewhere that there is only one cable going to the switch, that is a switch loop. Also open up the switch box and wrap the other end of that same white wire.
Next, permanently wrap (tag) the black wire of cable A with red tape. Since the switch is a switch loop, this cable is the only possible way the lights could possibly be receiving (switched) power.
Now grab your receptacle and some stripped Romex and sit at a convenient workbench. Put 6" pigtails of wire as follows. Use the screw terminals or screw-and-clamp if you have that type. Avoid backstabs (they're not reliable) and never use 12AWG on a backstab.
- Ground terminal: a bare (or green) wire.
- screw 1: a white wire.
- screw 2: nothing, but if the tab between 1 and 2 has been broken, a white wire.
- screw 3: a black wire.
- screw 4: nothing, but if the tab between 3 and 4 is broken, a black wire.
Ready?
Splice all same colors together.
See, what I did was color-code all the wires to their function rather than the default colors of /2 cable. The switch loop has only hot (black) and switched-hot (red). The wire to the lights needs switched-hot (red) and real neutral (white).
In new work, they commonly use red for the switched hot, because the law now requires neutral in switch loops (for smart switches). So they run some /3 cable up there.
Best Answer
If this is, in fact, a split outlet, you should be fine wire nutting the blacks and a black pigtail, the reds and a red pigtail, and you can connect the whites directly or wirenut them and a pigtail, as you prefer. You will need to break the tab connecting the receptacles on the hot side, at least (my guess is that they broke the hot tab and left the neutral tab connected, looking at the picture we're starting with.)
Connect that grounding wire to the new receptacle, as well...