Hmmmm. Trying to work in where the Monty Python 'watery bint' comes into the story. I guess the sword in the stone and the lady of the lake are two versions of the same myth.
Either that, or they were two distinct myths that were later conflated. In the early medieval Romances, the Lady's principle role was to beguile Merlin (and trap him in a tree!) and the sword in the stone was Excalibur. In later versions, the Lady of the Lake was the one who bestowed Excalibur to Arthur. Confusingly, Mallory tells both stories. Arthur receives Exalibur twice, once from the stone and again from the Lady, as if he'd somehow lost it in the woods and promptly forgotten about it.