posted 17 years ago
Hi Chethan,
If you maintain both List A and List B in sorted order, there's a simple linear-time algorithm for doing what you want. It's easier to demonstrate it than to explain it in words:
If your program can guarantee that both lists will always be kept in sorted order, then this algorithm should yield faster asymptotic performance than the algorithms you described. However, if you can't guarantee that, then you'll need to sort both lists before using this algorithm, in which case this may or may not be faster than your algorithms. It also won't work if your list elements aren't Comparable.
[ December 06, 2007: Message edited by: Kelvin Lim ]